On Hamilton decompositions of line graphs of non-Hamiltonian graphs and graphs without separating transitions

zbMATH Open1404.05164arXiv1710.06037MaRDI QIDQ4614042FDOQ4614042

Authors: Darryn Bryant, Barbara Maenhaut, Benjamin R. Smith 

Publication date: 30 January 2019

Abstract: In contrast with Kotzig's result that the line graph of a $3$-regular graph $X$ is Hamilton decomposable if and only if $X$ is Hamiltonian, we show that for each integer $kgeq4$ there exists a simple non-Hamiltonian $k$-regular graph whose line graph has a Hamilton decomposition. We also answer a question of Jackson by showing that for each integer $kgeq3$ there exists a simple connected $k$-regular graph with no separating transitions whose line graph has no Hamilton decomposition.

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

Recommendations

• Hamilton decompositions of line graphs of some bipartite graphs
• Two Hamiltonian cycles
• Hamilton cycle decomposition of line graphs and a conjecture of Bermond
• scientific article; zbMATH DE number 825148
• A new result on Hamilton line graph

zbMATH Keywords

line graphEuler toursisotropic systemsedge-disjoint Hamilton circuits

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Hamilton cycle decomposition of line graphs and a conjecture of Bermond
• Title not available (Why is that?)
• Cycles containing matchings and pairwise compatible euler tours
• Title not available (Why is that?)
• A Construction of a perfect set of Euler tours of K2k+1
• Hamilton decompositions of some line graphs
• Title not available (Why is that?)
• Research problems
• Decompositions of complete graphs into triangles and Hamilton cycles
• A characterisation of graphs having three pariwise compatible Euler tours
• The 1-factorization of some line-graphs
• On the maximum number of pairwise compatible euler cycles
• Hamilton decompositions of line graphs of some bipartite graphs

Cited In (2)

• Decomposable twofold triple systems with non-Hamiltonian 2-block intersection graphs
• Two Hamiltonian cycles

This page was built for publication: On Hamilton decompositions of line graphs of non-Hamiltonian graphs and graphs without separating transitions

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