Hamiltonian cycles in the square of a graph

MaRDI QIDQ648391zbMATH OpenFDO

Authors Jan Ekstein

Publication date 22 November 2011

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1206.4846, http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p203.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

block graphconnection of graphsHamiltonian cyclesquarestar

Mathematics Subject Classification ID

Paths and cycles (05C38) Connectivity (05C40) Eulerian and Hamiltonian graphs (05C45)

Abstract: We show that under certain conditions the square of the graph obtained by identifying a vertex in two graphs with hamiltonian square is also hamiltonian. Using this result, we prove necessary and sufficient conditions for hamiltonicity of the square of a connected graph such that every vertex of degree at least three in a block graph corresponds to a cut vertex and any two these vertices are at distance at least four.

Review text

Summary: We show that under certain conditions the square of the graph obtained by identifying a vertex in two graphs with hamiltonian square is also hamiltonian. Us- ing this result, we prove necessary and sufficient conditions for hamiltonicity of the square of a connected graph such that every vertex of degree at least three in a block graph corresponds to a cut vertex and any two these vertices are at distance at least four.

Recommendations

• On graphs whose square have strong Hamiltonian properties
• Induced \(S(K_{1,3})\) and hamiltonian cycles in the square of a graph
• On `maximal' Hamiltonian cycles in the square of a block
• scientific article; zbMATH DE number 4089598
• Characterizing forbidden pairs for Hamiltonian squares

Cited in

(19)

• On graphs whose square have strong Hamiltonian properties
• On `maximal' Hamiltonian cycles in the square of a block
• Induced \(S(K_{1,3})\) and hamiltonian cycles in the square of a graph
• A best possible result for the square of a 2-block to be Hamiltonian
• Connected even factors in the square of essentially 2-edge-connected graph
• Single-source three-disjoint path covers in cubes of connected graphs
• Computing square roots of trivially perfect and threshold graphs
• Disjoint path covers in cubes of connected graphs
• On box graph and its square
• scientific article; zbMATH DE number 5081142 (Why is no real title available?)
• scientific article; zbMATH DE number 3946176 (Why is no real title available?)
• scientific article; zbMATH DE number 4089597 (Why is no real title available?)
• scientific article; zbMATH DE number 4089598 (Why is no real title available?)
• A short proof of the versatile version of Fleischner's theorem
• The Square of a Hamiltonian Cycle
• Hamiltonian paths for involutions in the square of a Cayley graph
• On square-Hamiltonian graphs
• scientific article; zbMATH DE number 4189772 (Why is no real title available?)
• The most general structure of graphs with Hamiltonian or Hamiltonian connected square

This page was built for publication: 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 Q648391)