On vertex-disjoint cycles and degree sum conditions
| Autor: | Kazuhide Hirohata, Ariel Keller, Ronald J. Gould |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Discrete mathematics
Conjecture Degree (graph theory) 010102 general mathematics 0102 computer and information sciences Disjoint sets 01 natural sciences Graph Theoretical Computer Science Vertex (geometry) Combinatorics 010201 computation theory & mathematics Discrete Mathematics and Combinatorics 0101 mathematics Mathematics |
| Zdroj: | Discrete Mathematics. 341:203-212 |
| ISSN: | 0012-365X |
| DOI: | 10.1016/j.disc.2017.08.030 |
| Popis: | This paper considers a degree sum condition sufficient to imply the existence of k vertex-disjoint cycles in a graph G . For an integer t ≥ 1 , let σ t ( G ) be the smallest sum of degrees of t independent vertices of G . We prove that if G has order at least 7 k + 1 and σ 4 ( G ) ≥ 8 k − 3 , with k ≥ 2 , then G contains k vertex-disjoint cycles. We also show that the degree sum condition on σ 4 ( G ) is sharp and conjecture a degree sum condition on σ t ( G ) sufficient to imply G contains k vertex-disjoint cycles for k ≥ 2 . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect