Decomposable twofold triple systems with non-Hamiltonian 2-block intersection graphs (Q2223450)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Decomposable twofold triple systems with non-Hamiltonian 2-block intersection graphs |
scientific article |
Statements
Decomposable twofold triple systems with non-Hamiltonian 2-block intersection graphs (English)
0 references
29 January 2021
0 references
Summary: The \(2\)-block intersection graph \((2\)-BIG) of a twofold triple system (TTS) is the graph whose vertex set is composed of the blocks of the TTS and two vertices are joined by an edge if the corresponding blocks intersect in exactly two elements. The \(2\)-BIGs are themselves interesting graphs: each component is cubic and \(3\)-connected, and a \(2\)-BIG is bipartite exactly when the TTS is decomposable to two Steiner triple systems. Any connected bipartite \(2\)-BIG with no Hamilton cycle is a further counter-example to a disproved conjecture posed by \textit{W. T. Tutte} in [Discrete Math. 1, 203--208 (1971; Zbl 0219.05075)]. Our main result is that there exists an integer \(N\) such that for all \(v\geqslant N\), if \(v\equiv 1\) or \(3\bmod{6}\) then there exists a TTS \((v)\) whose \(2\)-BIG is bipartite and connected but not Hamiltonian. Furthermore, \(13<N\leqslant 663\). Our approach is to construct a TTS \((u)\) whose \(2\)-BIG is connected bipartite and non-Hamiltonian and embed it within a TTS \((v)\) where \(v>2u\) in such a way that, after a single trade, the \(2\)-BIG of the resulting TTS \((v)\) is bipartite connected and non-Hamiltonian.
0 references
Hamilton cycle
0 references
Steiner triple systems
0 references
0 references
0 references