Toughness, hamiltonicity and split graphs (Q1916113): Difference between revisions

The toughness of a finite undirected graph introduced by Chvátal plays an important role in connection with the hamiltonicity of a graph. For a non-complete graph \(G\) its toughness \(t(G)\) is defined as the minimum over all cutsets of the size of a cutset \(S\) divided by the number of connected components of the rest graph \(G-S\). A graph is \(t\)-tough if its toughness is at least \(t\). The authors study further properties related to hamiltonicity, traceability and toughness concepts. They present a polynomial time algorithm deciding whether the toughness of a given split graph is less than one and show that deciding whether the toughness of a bipartite graph is exactly one is coNP-complete. They show that every 3/2-tough split graph is hamiltonian and that there is a sequence of non-hamiltonian split graphs with toughness converging to 3/2.