Existence of two disjoint long cycles in graphs (Q2581410): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q4094891 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Degree conditions for 2-factors / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Some Theorems on Abstract Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Cycles and paths through specified vertices in k-connected graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the existence of disjoint cycles in a graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the maximum number of independent cycles in a graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4488568 / rank | |||
Normal rank |
Latest revision as of 14:52, 11 June 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