Existence of two disjoint long cycles in graphs (Q2581410)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Existence of two disjoint long cycles in graphs |
scientific article |
Statements
Existence of two disjoint long cycles in graphs (English)
0 references
10 January 2006
0 references
Following a conjecture by H. Wang in 2000, Egawa, and others, proved a theorem regarding the existence of \(k\) disjoint cycles in a graph. The authors now show that the 2-cycle version of that theorem holds as well: If \(n \geq 6\), \(h \geq 7\) are integers, and \(G\) is a graph of order \(n\) in which the degree sum of any pair of nonadjacent vertices is at least \(h\), then \(G\) contains two disjoint cycles having \(\geq\min\{ h,n \}\) vertices altogether. The proof requires an exhausting analysis of possible disjoint cycles in a counterexample.
0 references
cycle
0 references
subgraph
0 references
vertex-disjoint
0 references