All graphs with maximum degree three whose complements have 4-cycle decompositions (Q924981): Difference between revisions

From MaRDI portal
ReferenceBot (talk | contribs)
Changed an Item
Normalize DOI.
 
Property / DOI
 
Property / DOI: 10.1016/j.disc.2007.07.082 / rank
Normal rank
 
Property / DOI
 
Property / DOI: 10.1016/J.DISC.2007.07.082 / rank
 
Normal rank

Latest revision as of 08:15, 10 December 2024

scientific article
Language Label Description Also known as
English
All graphs with maximum degree three whose complements have 4-cycle decompositions
scientific article

    Statements

    All graphs with maximum degree three whose complements have 4-cycle decompositions (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    29 May 2008
    0 references
    A \(k\)-cycle system of a graph \(G\) is a partition of the edges of \(G\) into sets each of which induces a cycle of length \(k\). In the paper under review the authors classify the graphs of \(n\) vertices and maximal degree 3 whose complement in the complete graphs \(K_n\) admits a 4-cycle system. The main result shows that, with two explicitly shown exceptions, such graphs \(G\) of \(n\) vertices have to satisfy two conditions: all vertices must have odd degree and the number \(n(n-1)/2-|F(G)|\) must be divisible to 4.
    0 references
    4-cycle
    0 references
    3-regular
    0 references
    graph decomposition
    0 references

    Identifiers