Fair Hamilton decompositions of complete multipartite graphs (Q1850614): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
ReferenceBot (talk | contribs)
Changed an Item
 
(One intermediate revision by one other user not shown)
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1006/jctb.2001.2104 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2070602317 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Balanced Gray codes / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5650698 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A sufficient condition for equitable edge-colourings of simple graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Hamiltonian decompositions of complete graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Hamiltonian decompositions of complete regular s-partite graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: The embedding of partial triple systems when 4 divides \(\lambda\) / rank
 
Normal rank
Property / cites work
 
Property / cites work: Nondisconnecting disentanglements of amalgamated 2-factorizations of complete multipartite graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Solution of a Timetabling Problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Amalgamations of almost regular edge-colourings of simple graphs / rank
 
Normal rank

Latest revision as of 18:12, 4 June 2024

scientific article
Language Label Description Also known as
English
Fair Hamilton decompositions of complete multipartite graphs
scientific article

    Statements

    Fair Hamilton decompositions of complete multipartite graphs (English)
    0 references
    0 references
    0 references
    10 December 2002
    0 references
    A fair Hamilton decomposition of the complete multipartite graph \(G\) is a set of Hamilton cycles in \(G\) whose edges partition the edges of \(G\) in such a way that, for each pair of parts and for each pair of Hamiliton cycles \(H_1\) and \(H_2\), the difference in the number of edges in \(H_1\) and \(H_2\) joining vertices in these two parts is at most one. The authors prove the following theorem: There exists a fair Hamilton decomposition of \(K_{a_1,\ldots,a_p}\) if and only if \(a_1 = \cdots = a_p = m\) and \((p-1)m\) is even. The proof is constructive using graph homomorphisms which preserve the number of edges, but may identify adjacent vertices thereby generating (multiple) loops, which sometimes is called amalgamation.
    0 references
    graph homomorphisms
    0 references
    Hamilton cycles
    0 references
    0 references

    Identifiers