Thomassen’s conjecture for line graphs of 3-hypergraphs

Abstract

In 1986, Thomassen conjectured that every 4-connected line graph is hamiltonian. The conjecture is still wide open, and, as a possible approach to it, many statements that are equivalent or related to it have been studied. In this paper, we extend the statement to the class of line graphs of 3-hypergraphs, and generalize it to Tutte cycles and paths. Among others, we formulate the following conjectures: (i) every 2-connected line graph of a 3-hypergraph has a Tutte maximal cycle containing any two prescribed vertices, (ii) every 3-connected line graph of a 3-hypergraph has a Tutte maximal cycle containing any three prescribed vertices, (iii) every connected line graph of a 3-hypergraph has a Tutte maximal (a, b)-path for any two vertices a, b, (iv) every 4-connected line graph of a 3-hypergraph is Hamilton-connected, and we show that all these (seemingly much stronger) statements are equivalent with Thomassen’s conjecture.

V r. 1986 Thomassen formuloval hypotézu, podle které každý 4-souvislý hranový graf je hamiltonovský. Hypotéza je stále otevřená, a jako možný přístup k jejímu řešení byla studována řada tvrzení, která jsou s ní ekvivalentní. V článku rozšiřujeme hypotézu na hranové grafy 3-hypergrafů a zobecňujeme ji na Tutteovy kružnice a cesty. Mimo jiné formulujeme následující hypotézy: (i) každý 2-souvislý hranový graf 3-hypergrafu obsahuje Tutteovu maximální kružnici procházející libovolnými dvěma předepsanými uzly, (ii) každý 3-souvislý hranový graf 3-hypergrafu obsahuje Tutteovu maximální kružnici procházející libovolnými třemi předepsanými uzly, (iii) každý souvislý hranový graf 3-hypergrafu obsahuje Tutteovu maximální (a,b)-cestu pro každé dva uzly a, b, (iv) každý 4-souvislý hranový graf 3-hypergrafu je hamiltonovsky souvislý, a dokazujeme, že všechna tato (zdánlivě podstatně silnější) tvrzení jsou ekvivalentní s Thomassenovou hypotézou.