Abstract
Let k≥1 be an integer and G=(V 1,V 2;E) a bipartite graph with |V 1|=|V 2|=n such that n≥2k+2. Our result is as follows: If \(d(x)+d(y)\geq \lceil\frac{4n+k}{3}\rceil\) for any nonadjacent vertices x∈V 1 and y∈V 2, then for any k distinct vertices z 1,…,z k , G contains a 2-factor with k+1 cycles C 1,…,C k+1 such that z i ∈V(C i ) and l(C i )=4 for each i∈{1,…,k}.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alon, N., Yuster, R.: H-factors in dense graphs. J. Comb. Theory Ser. B 66, 269–282 (1996)
Bondy, J.A., Chvátal, V.: A method in graph theory. Discrete Math. 15, 111–135 (1976)
Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. North-Holland, Amsterdam (1976)
Brandt, S., Chen, G., Faudree, R., Gould, R.J., Lesniak, L.: Degree conditions for 2-factors. J. Graph Theory 24, 165–173 (1997)
Corrádi, K., Hajnal, A.: On the maximal number of independent circuits in a graph. Acta Math. Acad. Sci. Hung. 14, 423–439 (1963)
EI-Zahar, M.: On circuits in graphs. Discrete Math. 50, 227–230 (1984)
Johansson, R.: On the bipartite case of EI-Zahar’s conjecture. Discrete Math. 219, 123–134 (2000)
Komlós, J., Sáközy, G.N., Szemerédi, E.: Proof of the Alon-Yuster conjecture. Discrete Math. 235, 255–269 (2001)
Matsumura, H.: Vertex-disjoint 4-cycles containing specified edges in a bipartite graph. Discrete Math. 297, 78–90 (2005)
Wang, H.: On 2-factors of a bipartite graph. J. Graph Theory 31, 101–106 (1999)
Yan, J., Liu, G.: On 2-factors with prescribed properties in a bipartite graph. Acta Math. Sin. Engl. Ser. 22, 1115–1120 (2006)
Yan, J., Liu, G.: On 2-factors with cycles containing specified edges in a bipartite graph. Discrete Math. (2008). doi:10.1016/j.disc.2007.11.072
Author information
Authors and Affiliations
Corresponding author
Additional information
The research of J. Yan was supported by the Foundation for the distinguished young scholars of Shandong province (No. 2007BS01021) and the Taishan scholar fund from Shandong province. It is also sponsored by SRF for ROCS, SEM.
The research of G. Li was supported by research grants from NSFC under grant numbers: 60373025, 60673059; and also by Taishan scholar fund from Shandong province.
Rights and permissions
About this article
Cite this article
Gao, Y., Yan, J. & Li, G. On 2-factors with cycles containing specified vertices in a bipartite graph. J. Appl. Math. Comput. 31, 203–215 (2009). https://doi.org/10.1007/s12190-008-0202-9
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12190-008-0202-9