On 2-factors with cycles containing specified vertices in a bipartite graph

被引：3
作者：
Gao Y. [1 ]
Yan J. [1 ]
Li G. [1 ]
机构：
[1] School of Mathematics, Shandong University
来源：
Journal of Applied Mathematics and Computing | 2009年 / 31卷 / 1-2期
基金：
中国国家自然科学基金;
关键词：
2-factor; Bipartite graph; Quadrilateral; Vertex-disjoint;
D O I：
10.1007/s12190-008-0202-9
中图分类号：
学科分类号：
摘要：
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)≥{4n+k}{3} 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}. © 2008 Korean Society for Computational and Applied Mathematics.
引用
收藏
页码：203 / 215
页数：12
相关论文
共 11 条
  • [1] Alon N., Yuster R., H-factors in dense graphs, J. Comb. Theory Ser. B, 66, pp. 269-282, (1996)
  • [2] Bondy J.A., Chvatal V., A method in graph theory, Discrete Math., 15, pp. 111-135, (1976)
  • [3] Bondy J.A., Murty U.S.R., Graph Theory with Applications, (1976)
  • [4] Brandt S., Chen G., Faudree R., Gould R.J., Lesniak L., Degree conditions for 2-factors, J. Graph Theory, 24, pp. 165-173, (1997)
  • [5] Corradi K., Hajnal A., On the maximal number of independent circuits in a graph, Acta Math. Acad. Sci. Hung., 14, pp. 423-439, (1963)
  • [6] EI-Zahar M., On circuits in graphs, Discrete Math., 50, pp. 227-230, (1984)
  • [7] Johansson R., On the bipartite case of EI-Zahar’s conjecture, Discrete Math., 219, pp. 123-134, (2000)
  • [8] Komlos J., Sakozy G.N., Szemeredi E., Proof of the Alon-Yuster conjecture, Discrete Math., 235, pp. 255-269, (2001)
  • [9] Matsumura H., Vertex-disjoint 4-cycles containing specified edges in a bipartite graph, Discrete Math., 297, pp. 78-90, (2005)
  • [10] Wang H., On 2-factors of a bipartite graph, J. Graph Theory, 31, pp. 101-106, (1999)
12