On Hamiltonian properties of \(K_{1, r}\)-free split graphs (Q6041859): Difference between revisions

For \(r\geq 3\), a graph \(G\) is \(K_{1, r}\)-free if \(G\) does not have an induced subgraph isomorphic to \(K_{1, r}\). A graph \(G\) is fully cycle extendable if every vertex in \(G\) lies on a cycle of length 3 and every non-Hamiltonian cycle in \(G\) is extendable. A connected graph \(G\) is a split graph if the vertex set of \(G\) can be partitioned into a clique and a stable set. The authors introduce a certain type of alternating paths in the study of Hamiltonian properties of split graphs and prove that a split graph \(G\) is Hamiltonian if and only if \(G\) is fully cycle extendable. As a result, for \(r\in\{3, 4\}\), every \(r\)-connected \(K_{1, r}\)-free split graph is Hamilton-connected and every \((r-1)\)-connected \(K_{1,r}\)-free split graph is fully cycle extendable.