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
    0 references
    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
    0 references
    0 references
    Hamiltonian connectedness
    0 references
    claw-free graph
    0 references
    Hamiltonian-connected
    0 references