Existence of two disjoint long cycles in graphs (Q2581410): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.disc.2005.10.017 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2091613024 / rank | |||
Normal rank |
Revision as of 03:27, 20 March 2024
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