Hamiltonian connectedness in claw-free graphs (Q5906903)
From MaRDI portal
scientific article; zbMATH DE number 1146346
Language | Label | Description | Also known as |
---|---|---|---|
English | Hamiltonian connectedness in claw-free graphs |
scientific article; zbMATH DE number 1146346 |
Statements
Hamiltonian connectedness in claw-free graphs (English)
0 references
14 September 1998
0 references
Let be \(G\) a 3-connected claw-free graph (i.e. \(G\) does not contain \(K_{1,3}\) as an induced subgraph) and \(H\) a subgraph of \(G\) with \(\overline\alpha_3(H)\leq\chi(G)-1\), where \(\alpha_3(H)\) is the maximum number of vertices of \(H\) that are pairwise at a distance of at least three in \(G\) and \(\overline\alpha_3(H)=|\overline\Theta_3(H)|\) with \(\overline\Theta_3(H)\) an independent set of \(V(H)\) containing all vertices of \(\Theta_3(H)\), a set of vertices of \(H\) with cardinality \(\alpha_3(H)\) which are pairwise at a distance of at least three, and some vertex \(x\) having at most two neighbours \(u,v\) such that \(u,v\notin\Theta_3(H)\) and \(u\) and \(v\) are respectively adjacent to at most one vertex of \(\Theta_3(H)\). The author proves that in this case \(G\) is Hamiltonian-connected, which generalizes a result of Z. Wu, Q. Cha and T. Jin.
0 references
Hamiltonian connectedness
0 references
claw-free graph
0 references
Hamiltonian-connected
0 references