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 | |||
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
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