Premium
Decomposing Graphs of High Minimum Degree into 4‐Cycles
Author(s) -
Bryant Darryn,
Cavenagh Nicholas J.
Publication year - 2015
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21816
Subject(s) - combinatorics , mathematics , bipartite graph , degree (music) , simple graph , disjoint sets , vertex (graph theory) , discrete mathematics , graph , frequency partition of a graph , simple (philosophy) , graph power , line graph , philosophy , physics , epistemology , acoustics
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 ( 31 32 + o n ( 1 ) ) n , 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 ( 1 − 10 − 94 + o n ( 1 ) ) n . 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 degree3 5 n − 1 , 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 ( 31 32 + o n ( 1 ) ) n .