Abstract
Let k be a positive integer and let G be a graph of order n ≥ 3k + 1, X be a set of any k distinct vertices of G. It is proved that if \( d\left( x \right) + d\left( y \right) \ge n + 2k - 2\) for any pair of nonadjacent vertices \(x,y \in V\left( G \right)\), then G contains k disjoint cycles T 1, ⋯ ,T k such that each cycle contains exactly one vertex in X, and \(\left| {{T_i}} \right| = 3\) for each 1 ≤ i ≤ k or \(\left| {{T_k}} \right| = 4\) and the rest are all triangles. We also obtained two results about disjoint 6-cycles in a bipartite graph.
Supported by the National Natural Science Foundation of China (Grant No. 11161035), Ningxia Ziran (Grant No. NZ1153) and research grant from Ningxia University (Grant No. ndzr10-19).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. North-Holland, Amsterdam (1976)
Corrádi, K., Hajnal, A.: On the maximal number of independent circuits in a graph. Acta Math. Acad. Sci. Hungar 14, 423–439 (1963)
Dirac, G.A.: On the maximal number of independent triangles. Abh. Math. Debrecen 9, 78–82 (1963)
Dong, J.: k disjoint cycles containing specified independent vertices. Discrete Math. 308, 5269–5273 (2008)
Justesen, P.: On Independent Circuits in Finite Graphs and a Conjecture of Erdös and Pósa. Annals of Discrete Mathematics 41, 299–306 (1989)
Li, H., Li, J.: Independent triangle covering given vertices of a graph. Theoretical Computer Science 263, 333–344 (2001)
Zhu, S., Hao, R.: Disjoint 6-cycles in Bipartite Graphs. Advances in Mathematics 36, 617–626 (2007)
Psa, L.: On The Circuits Of Finite Graphs. Magyar Tud. Akad. Mat. Kutató Int. Kőzl 8, 355–361 (1964)
Wang, H.: On The Maximum Number Of Independent Cycles In A Graph. Discrete Math. 205, 183–190 (1999)
Lesniak, L.: Independent Cycles In Graphs. J. Combin. Math. Combin. Comput. 17, 55–63 (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ma, D., Gao, Y. (2013). Disjoint Small Cycles in Graphs and Bipartite Graphs. In: Fellows, M., Tan, X., Zhu, B. (eds) Frontiers in Algorithmics and Algorithmic Aspects in Information and Management. Lecture Notes in Computer Science, vol 7924. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38756-2_3
Download citation
DOI: https://doi.org/10.1007/978-3-642-38756-2_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38755-5
Online ISBN: 978-3-642-38756-2
eBook Packages: Computer ScienceComputer Science (R0)