Euler cycles in the complete graph K₂m+1

DOI10.1016/S0012-365X(96)00074-XMaRDI QIDQ1363690zbMATH OpenOpenAlexFDO

Authors Tomáš Dvořák, Petr Liebl, Ivan Havel

Publication date 10 August 1997

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(96)00074-x

zbMATH Keywords

complete graphdecompositionEuler cycleharmonious chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

The authors analyze the freedom one has when walking along an Euler cycle through a complete graph of odd order. They show that for any cycle \(C\) of \({2m+1\choose 2}\) vertices, \(2m+1\) of them being black, the rest of them being white, there exists an edge monomorphism of \(C\) onto \(K_{2m+1}\) injective on the set of black vertices of \(C\) if \(m\neq 2\) or if \(m=2\) and the 5 black vertices of \(C\) are not colored in two special ways. Their proof is constructive. However, they also relied on computers to verify approximately 37,000 cases needed for the induction basis. Their theorem generalizes a previous result on the decomposition of \(K_{2m+1}\) into edge-disjoint trails of given lengths. In addition, a relation to the concept of harmonious chromatic number is also discussed.

Recommendations

• Euler cycles in \(K_{2m}\) plus perfect matching
• Cycles, Eulerian digraphs and the Schönemann-Gauss theorem
• Eulerian cycle decomposition conjecture for the line graph of complete graphs
• A cycle decomposition conjecture for Eulerian graphs
• scientific article; zbMATH DE number 2145386
• \(k\)-cyclic even cycle systems of the complete graph
• On the Eulerian cycle decomposition conjecture and complete multipartite graphs
• Eulerian straight ahead cycles in drawings of complete bipartite graphs
• Cycles through k+2 vertices in k-connected graphs
• A special construction of complete Euler graphs

Cites work

• An upper bound for the harmonious chromatic number of a graph
• Decomposition of a complete graph into trails of given lengths
• Decompositions En Chaines D'un Graphe Complet D'ordre Impair
• scientific article; zbMATH DE number 3637904 (Why is no real title available?)

Cited in

(5)

• Euler cycles in \(K_{2m}\) plus perfect matching
• On the Eulerian cycle decomposition conjecture and complete multipartite graphs
• Perfect set of Euler tours of \(K_{p,p,p}\)
• A Construction of a perfect set of Euler tours of K2k+1
• The edge-distinguishing chromatic number of petal graphs, chorded cycles, and spider graphs

This page was built for publication: Euler cycles in the complete graph \(K_{2m+1}\)

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