Decomposing Graphs of High Minimum Degree into 4‐Cycles |
| |
Authors: | Darryn Bryant Nicholas J Cavenagh |
| |
Institution: | 1. DEPARTMENT OF MATHEMATICS, THE UNIVERSITY OF QUEENSLAND, QUEENSLAND, AUSTRALIA;2. DEPARTMENT OF MATHEMATICS, THE UNIVERSITY OF WAIKATO, HAMILTON, NEW ZEALAND |
| |
Abstract: | If a graph G decomposes into edge‐disjoint 4‐cycles, then each vertex of G has even degree and 4 divides the number of edges in G. It is shown that these obvious necessary conditions are also sufficient when G is any simple graph having minimum degree at least , where n is the number of vertices in G. This improves the bound given by Gustavsson (PhD Thesis, University of Stockholm, 1991), who showed (as part of a more general result) sufficiency for simple graphs with minimum degree at least . On the other hand, it is known that for arbitrarily large values of n there exist simple graphs satisfying the obvious necessary conditions, having n vertices and minimum degree , but having no decomposition into edge‐disjoint 4‐cycles. We also show that if G is a bipartite simple graph with n vertices in each part, then the obvious necessary conditions for G to decompose into 4‐cycles are sufficient when G has minimum degree at least . |
| |
Keywords: | cycle decomposition graph decomposition |
|
|