Decomposing Graphs of High Minimum Degree into 4-Cycles
| Autor: | Darryn Bryant, Nicholas J. Cavenagh |
|---|---|
| Rok vydání: | 2014 |
| Předmět: |
Discrete mathematics
010102 general mathematics Neighbourhood (graph theory) 0102 computer and information sciences 16. Peace & justice 01 natural sciences Combinatorics 010201 computation theory & mathematics Graph power Frequency partition of a graph Random regular graph Bipartite graph Discrete Mathematics and Combinatorics Bound graph Path graph Geometry and Topology Graph toughness 0101 mathematics Mathematics |
| Zdroj: | Journal of Graph Theory. 79:167-177 |
| ISSN: | 0364-9024 |
| DOI: | 10.1002/jgt.21816 |
| Popis: | 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 3132+on1n, 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+on1n. 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 35n-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 3132+on1n. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text