Quadrangularly connected claw-free graphs

DOI10.1016/J.DISC.2006.07.034MaRDI QIDQ870987zbMATH OpenOpenAlexFDO

Authors Cheng Guo, Dengxin Li, Hong-Jian Lai, Mingchu Li, Liming Xiong

Publication date 15 March 2007

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2006.07.034

zbMATH Keywords

claw-free graphsquadrangular connectivity

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45)

Review text

Let \(G_1\) be a graph arising from the cycle \(C_8\) with vertices \(x_1,x_2,\dots ,x_8\) by adding the edges of the cycle \(C_4\) with vertices \(x_1,x_3,x_5,x_7\) and let \(G_2\) be the graph obtained from \(G_1\) by adding the edge \(x_1x_5\). Let \(N(v,G)\) be the subgraph of a graph \(G\) induced by the set of all vertices adjacent to the vertex \(v\). \(G\) is quadrangularly connected if for every two edges \(e_1,e_2\) of \(G\) there is a sequence of cycles of length 3 or 4, \(C_1,C_2,\dots,C_r\), such that \(e_1\in E(C_1), e_2\in E(C_r)\) and \(E(C_i)\cap E(C_{i+1})\neq\emptyset\) for \(i=1,2,\dots,r-1\). It is shown that if \(G\) is a quadrangularly connected claw-free graph, which does not contain \(G_1\) or \(G_2\) as an induced subgraph and \(N(v,G)\) is disconnected for every vertex \(v\) of degree 4, then \(G\) is Hamiltonian.

Recommendations

• Vertex pancyclicity of quadrangularly connected claw-free graphs
• Hamiltonicity of 2-connected quasi-claw-free graphs
• Hamiltonian connectedness in claw-free graphs
• Full cycle extendability of nearly claw-free graphs.
• Hamiltonicity of 3-connected quasi-claw-free graphs.

Cites work

• Every connected, locally connected nontrivial graph with no induced claw is hamiltonian
• Graph theory
• Hamiltonian circuits in N₂‐locally connected K_1,3‐free graphs
• HamiltonianN2-locally connected claw-free graphs
• scientific article; zbMATH DE number 2188401 (Why is no real title available?)
• On a closure concept in claw-free graphs
• On pancyclic claw-free graphs

Cited in

(7)

• On 4-connected claw-free well-covered graphs
• On quadrilaterals and 4-path in claw-free graphs
• scientific article; zbMATH DE number 5525657 (Why is no real title available?)
• Full cycle extendability of locally connected \(K_{1,4}\)-restricted graphs
• Hamiltonian properties of locally connected graphs with bounded vertex degree
• On Hamiltonicity of 3-connected claw-free graphs
• Vertex pancyclicity of quadrangularly connected claw-free graphs

This page was built for publication: Quadrangularly connected claw-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q870987)