Sharp minimum degree conditions for the existence of disjoint theta graphs

DOI10.37236/9670MaRDI QIDQ820839zbMATH OpenOpenAlexFDO

Authors Michael Santana, Emily A. Marshall

Publication date 28 September 2021

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.37236/9670

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

even cycleminimum degreetheta graphvertex-disjoint cycles

Mathematics Subject Classification ID

Vertex degrees (05C07) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

Summary: In [Acta Math. Acad. Sci. Hung. 14, 423--439 (1963; Zbl 0118.19001)], \textit{K. Corradi} and \textit{A. Hajnal} showed that if \(G\) is an \(n\)-vertex graph with \(n \geqslant 3k\) and \(\delta(G) \geqslant 2k\), then \(G\) will contain \(k\) disjoint cycles; furthermore, this result is best possible, both in terms of the number of vertices as well as the minimum degree. In this paper we focus on an analogue of this result for theta graphs. Results from \textit{K.-i. Kawarabayashi} [J. Graph Theory 39, No. 2, 111--128 (2002; Zbl 0992.05059)] and \textit{S. Chiba} et al. [Adv. Appl. Math. 54, 105--120 (2014; Zbl 1284.05209)] showed that if \(n = 4k\) and \(\delta(G) \geqslant \lceil \frac{5}{2}k \rceil \), or if \(n\) is large with respect to \(k\) and \(\delta(G) \ge 2k+1\), respectively, then \(G\) contains \(k\) disjoint theta graphs. While the minimum degree condition in both results are sharp for the number of vertices considered, this leaves a gap in which no sufficient minimum degree condition is known. Our main result in this paper resolves this by showing if \(n \geqslant 4k\) and \(\delta(G) \geqslant \lceil \frac{5}{2}k\rceil \), then \(G\) contains \(k\) disjoint theta graphs. Furthermore, we show this minimum degree condition is sharp for more than just \(n = 4k\), and we discuss how and when the sharp minimum degree condition may transition from \(\lceil \frac{5}{2}k\rceil\) to \(2k+1\).

Recommendations

• SUFFICIENT CONDITION FOR THE EXISTENCE OF THREE DISJOINT THETA GRAPHS
• Disjoint even cycles packing
• The extremal function for three disjoint theta graphs.
• The extremal function for two disjoint cycles
• Independence number and disjoint theta graphs

Cites work

• K₄⁻‐factor in a graph
• An Ore-type theorem for perfect packings in graphs
• Disjoint chorded cycles in graphs
• Disjoint cycles and chorded cycles in a graph with given minimum degree
• Independet cycles and chorded cycles in graphs
• Minimum degree conditions for vertex-disjoint even cycles in large graphs
• On the maximal number of independent circuits in a graph
• On the number of independent chorded cycles in a graph
• Tiling Turán theorems
• Vertex-disjoint copies of K₄^-

Cited in

(5)

• Disjoint even cycles packing
• The extremal function for three disjoint theta graphs.
• SUFFICIENT CONDITION FOR THE EXISTENCE OF THREE DISJOINT THETA GRAPHS
• Independence number and disjoint theta graphs
• The extremal function for two disjoint cycles

This page was built for publication: Sharp minimum degree conditions for the existence of disjoint theta graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q820839)