Degree Sum Conditions for Cyclability in Bipartite Graphs

被引:0
作者
Okamura, Haruko [1 ]
Yamashita, Tomoki [1 ]
机构
[1] Kinki Univ, Dept Math, Higashiosaka, Osaka 5778502, Japan
关键词
Cycle; Cyclability; Bipartite graph; Degree sum; LONG CYCLES;
D O I
10.1007/s00373-012-1148-0
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
We denote by G[X, Y] a bipartite graph G with partite sets X and Y. Let d (G) (v) be the degree of a vertex v in a graph G. For G[X, Y] and we define . Amar et al. (Opusc. Math. 29:345-364, 2009) obtained sigma (1,1)(S) condition for cyclability of balanced bipartite graphs. In this paper, we generalize the result as it includes the case of unbalanced bipartite graphs: if G[X, Y] is a 2-connected bipartite graph with |X| a parts per thousand yen |Y| and such that sigma (1,1)(S) a parts per thousand yen |X| + 1, then either there exists a cycle containing S or and there exists a cycle containing Y. This degree sum condition is sharp.
引用
收藏
页码:1077 / 1085
页数:9
相关论文
共 10 条
[1]   CYCLABILITY IN BIPARTITE GRAPHS [J].
Amar, Denise ;
Flandrin, Evelyne ;
Gancarzewicz, Grzegorz .
OPUSCULA MATHEMATICA, 2009, 29 (04) :345-364
[2]  
Bondy J.A., 2008, GTM
[3]  
Broersma H.J., DEGREE CONDITIONS DO
[4]   LONG CYCLES IN BIPARTITE GRAPHS [J].
JACKSON, B .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1985, 38 (02) :118-131
[5]  
Kaneko A., LONGEST CYCLES BALAN
[6]   ON HAMILTONIAN BIPARTITE GRAPHS [J].
MOON, J ;
MOSER, L .
ISRAEL JOURNAL OF MATHEMATICS, 1963, 1 (03) :163-&
[7]   A Degree Sum Condition Concerning the Connectivity and the Independence Number of a Graph [J].
Ozeki, Kenta ;
Yamashita, Tomoki .
GRAPHS AND COMBINATORICS, 2008, 24 (05) :469-483
[8]  
SHI RH, 1992, J GRAPH THEOR, V16, P267
[9]   On long cycles in a 2-connected bipartite graph [J].
Wang, H .
GRAPHS AND COMBINATORICS, 1996, 12 (04) :373-384
[10]  
Zuluaga C., 1977, I WISS Z TH ILMENAU, V23, P57