An Algorithmic Answer to the Ore-Type Version of Dirac’s Question on Disjoint Cycles

H. A. Kierstead (), A. V. Kostochka (), T. Molla () and D. Yager ()
Additional contact information
H. A. Kierstead: Arizona State University
A. V. Kostochka: University of Illinois
T. Molla: University of South Florida
D. Yager: University of Illinois

A chapter in Optimization Problems in Graph Theory, 2018, pp 149-168 from Springer

Abstract: Abstract Corrádi and Hajnal in 1963 proved the following theorem on the NP-complete problem on the existence of k disjoint cycles in an n-vertex graph G: For all k ≥ 1 and n ≥ 3k, every (simple) n-vertex graph G with minimum degree δ(G) ≥ 2k contains k disjoint cycles. The same year, Dirac described the 3-connected multigraphs not containing two disjoint cycles and asked the more general question: Which (2k − 1)-connected multigraphs do not contain k disjoint cycles? Recently, Kierstead, Kostochka, and Yeager resolved this question. In this paper, we sharpen this result by presenting a description that can be checked in polynomial time of all multigraphs G with no k disjoint cycles for which the underlying simple graph G ̲ $$ \underline {G}$$ satisfies the following Ore-type condition: d G ̲ ( v ) + d G ̲ ( u ) ≥ 4 k − 3 $$d_{ \underline {G}}(v)+d_{ \underline {G}}(u)\geq 4k-3$$ for all nonadjacent u, v ∈ V (G).

Date: 2018
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-319-94830-0_8

Ordering information: This item can be ordered from
http://www.springer.com/9783319948300

DOI: 10.1007/978-3-319-94830-0_8

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().