Induced S(K₁,3) and hamiltonian cycles in the square of a graph

DOI10.1016/S0012-365X(99)00115-6MaRDI QIDQ1817578zbMATH OpenWikidataFDO

Authors Mohamed El Kadi Abderrezzak, Evelyne Flandrin, Zdeněk Ryjáček

Publication date 29 June 2000

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(99)00115-6

zbMATH Keywords

hamiltonian cyclesquare of a graph

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45)

Review text

The square of a graph \(G\) is the the graph with vertex set \(V(G)\) in which two vertices are adjacent if their distance in \(G\) is one or two. The graph \(S(K_{1,3})\) is the graph \(K_{1,3}\) in which each edge is subdivided once. The degree of a block \(B\) of a graph \(G\) is the number of cut vertices of \(G\) belonging to \(V(B)\). The paper proves that the square of a connected graph in which every induced \(S(K_{1,3})\) has at least three edges in a block of degree at most 2 is hamiltonian. It is also shown that insertion of a block of degree 2 into, or under certain conditions also deletion of such a block from, a connected graph does not change the hamiltonicity of the square of the graph.

Recommendations

• scientific article; zbMATH DE number 3989386
• Hamiltonian cycles in the square of a graph
• On graphs whose square have strong Hamiltonian properties
• scientific article; zbMATH DE number 4089598
• On `maximal' Hamiltonian cycles in the square of a block

Cited in

(13)

• On graphs whose square have strong Hamiltonian properties
• Trestles in the squares of graphs
• Connected even factors in the square of essentially 2-edge-connected graph
• Single-source three-disjoint path covers in cubes of connected graphs
• Disjoint path covers in cubes of connected graphs
• On box graph and its square
• scientific article; zbMATH DE number 3989386 (Why is no real title available?)
• The square of a connected S(K1,3)-free graph is vertex pancyclic
• A short proof of the versatile version of Fleischner's theorem
• Cycles in squares of trees without generalized claws
• Star subdivisions and connected even factors in the square of a graph
• scientific article; zbMATH DE number 4189772 (Why is no real title available?)
• Hamiltonian cycles in the square of a graph

This page was built for publication: Induced \(S(K_{1,3})\) and hamiltonian cycles in the square of a graph

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