Abstract
Let k be an integer with k ≥ 2 and G a graph with order n > 4k. We prove that if the minimum degree sum of any two nonadjacent vertices is at least n + k, then G contains a vertex cover with exactly k components such that k−1 of them are chorded 4-cycles. The degree condition is sharp in general.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications. North-Holland, Amsterdam, 1976
Enomoto, H.: Graph partition problems into cycles and paths. Discrete Math., 233, 93–101 (2001)
Yan, J.: Disjoint triangles and quadrilaterals in a graph. Discrete Math., 308, 3930–3937 (2008)
Fujita, S.: Vertex-disjoint copies of K −4 in graphs. Australas. J. Combin., 31, 189–200 (2005)
Kawarabayashi, K.: K −4 -factor in a graph. J. Graph Theory, 39, 111–128 (1999)
Gould, R. J.: A look at cycles containing specified elements of a graph. Discrete Math., 309, 6299–6311 (2009)
Brandt, S., Chen, G., Faudree, R., et al.: Degree conditions for 2-factors. J. Graph Theory, 24, 165–173 (1997)
Gao, Y., Yan, J., Li, G.: On 2-factors with chorded quadrilaterals in graphs. Ars Combin., 98, 193–201 (2011)
Wang, H.: Covering a graph with cycles. J. Graph Theory, 20, 203–211 (1995)
Bondy, J. A., Chvátal, V.: A method in graph theory. Discrete Math., 15, 111–135 (1976)
Ore, O.: Note on Hamiltonian circuits. Amer. Math. Monthly, 67, 55 (1960)
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by Natural Science Foundation of China (Grant Nos. 11161035, 10801091), Research Grants from Ningxia University (Grant No. (E)ndzr09-1) and Scientific Research Project in Xinjiang (Grant No. XJEDU2009S101)
Rights and permissions
About this article
Cite this article
Gao, Y.S., Li, G.J. & Yan, J. A vertex cover with chorded 4-cycles. Acta. Math. Sin.-English Ser. 27, 2351–2360 (2011). https://doi.org/10.1007/s10114-011-9531-y
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10114-011-9531-y