Two Hamiltonian cycles

DOI10.1016/J.DISC.2022.112797zbMATH Open1484.05118arXiv2106.10368OpenAlexW4205863211WikidataQ114190559 ScholiaQ114190559MaRDI QIDQ2113347FDOQ2113347

Vaidy Sivaraman, Thomas Zaslavsky

Publication date: 14 March 2022

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: If the line graph of a graph $G$ decomposes into Hamiltonian cycles, what is $G$? We answer this question for decomposition into two cycles.

Full work available at URL: https://arxiv.org/abs/2106.10368

Recommendations

• Hamilton cycle decomposition of line graphs and a conjecture of Bermond
• scientific article; zbMATH DE number 2197884
• Hamilton decompositions of line graphs of some bipartite graphs
• A new result on Hamilton line graph
• On Hamilton decompositions of line graphs of non-Hamiltonian graphs and graphs without separating transitions

zbMATH Keywords

line graphHamilton decomposition

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• The Planar Hamiltonian Circuit Problem is NP-Complete
• Hamilton cycle decomposition of line graphs and a conjecture of Bermond
• From the theory of regular graphs of third and fourth degree
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• NP-completeness of some problems of partitioning and covering in graphs
• Cycles Hamiltoniens dans les graphes 4-réguliers 4-connexes
• Title not available (Why is that?)
• On Hamilton Decompositions of Line Graphs of Non-Hamiltonian Graphs and Graphs without Separating Transitions

Cited In (4)

• Hamilton decompositions of some line graphs
• On 2-pyramidal Hamiltonian cycle systems
• Title not available (Why is that?)
• Dual power assignment via second Hamiltonian cycle

This page was built for publication: Two Hamiltonian cycles

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