Euler cycles in the complete graph \(K_{2m+1}\) (Q1363690): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Added link to MaRDI item.
links / mardi / namelinks / mardi / name
 

Revision as of 14:51, 31 January 2024

scientific article
Language Label Description Also known as
English
Euler cycles in the complete graph \(K_{2m+1}\)
scientific article

    Statements

    Euler cycles in the complete graph \(K_{2m+1}\) (English)
    0 references
    0 references
    0 references
    0 references
    10 August 1997
    0 references
    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.
    0 references
    Euler cycle
    0 references
    complete graph
    0 references
    decomposition
    0 references
    harmonious chromatic number
    0 references

    Identifiers