×

zbMATH — the first resource for mathematics

On independent triples and vertex-disjoint chorded cycles in graphs. (English) Zbl 1444.05077
Summary: Let \(G\) be a graph, and let \(\sigma_3(G)\) be the minimum degree sum of three independent vertices of \(G\). We prove that if \(G\) is a graph of order at least \(8k+5\) and \(\sigma_3(G)\geq 9k-2\) with \(k\geq 1\), then \(G\) contains \(k\) vertex-disjoint chorded cycles. We also show that the degree sum condition on \(\sigma_3(G)\) is sharp.
MSC:
05C38 Paths and cycles
PDF BibTeX XML Cite
Full Text: Link
References:
[1] S. Chiba, S. Fujita, Y. Gao and G. Li, On a sharp degree sum condition for disjoint chorded cycles in graphs,Graphs Combin.26 (2010), 173-186. · Zbl 1231.05143
[2] S. Chiba and T. Yamashita, Degree conditions for the existence of vertex-disjoint cycles and paths: A survey,Graphs Combin.34 (2018), 1-83. · Zbl 1382.05017
[3] K. Corr´adi and A. Hajnal, On the maximal number of independent circuits in a graph,Acta Math. Acad. Sci. Hungar.14 (1963), 423-439.
[4] H. Enomoto, On the existence of disjoint cycles in a graph,Combinatorica18 (4) (1998), 487-492. · Zbl 0924.05041
[5] D. Finkel, On the number of independent chorded cycles in a graph,Discrete Math.308 (22) (2008), 5265-5268. · Zbl 1228.05170
[6] S. Fujita, H. Matsumura, M. Tsugaki and T. Yamashita, Degree sum conditions and vertex-disjoint cycles in a graph,Australas. J. Combin.35 (2006), 237-251. · Zbl 1096.05029
[7] Y. Gao, X. Lin and H. Wang, Vertex-disjoint double chorded cycles in bipartite graphs,Discrete Math.342 (9) (2019), 2482-2492. · Zbl 1416.05226
[8] R. J. Gould, Graph Theory, Dover Pub. Inc. Mineola, N.Y. 2012. · Zbl 1284.05003
[9] R. J. Gould, K. Hirohata and A. Keller, On vertex-disjoint cycles and degree sum conditions,Discrete Math.341 (1) (2018), 203-212. · Zbl 1372.05111
[10] T. Molla, M. Santana and E. Yeager, Disjoint cycles and chorded cycles in a graph with given minimum degree,Discrete Math.343 (6) (2020), 111837. · Zbl 1437.05117
[11] H.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.