Degree Sum Conditions for Cyclability in Bipartite Graphs

被引:0
作者
Haruko Okamura
Tomoki Yamashita
机构
[1] Kinki University,Department of Mathematics
来源
Graphs and Combinatorics | 2013年 / 29卷
关键词
Cycle; Cyclability; Bipartite graph; Degree sum;
D O I
暂无
中图分类号
学科分类号
摘要
We denote by G[X, Y] a bipartite graph G with partite sets X and Y. Let dG(v) be the degree of a vertex v in a graph G. For G[X, Y] and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${S \subseteq V(G),}$$\end{document} we define \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\sigma_{1,1}(S):=\min\{d_G(x)+d_G(y) : (x,y) \in (X \cap S,Y) \cup (X, Y \cap S), xy \not\in E(G)\}}$$\end{document} . Amar et al. (Opusc. Math. 29:345–364, 2009) obtained σ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| ≥ |Y| and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${S \subseteq V(G)}$$\end{document} such that σ1,1(S) ≥ |X| + 1, then either there exists a cycle containing S or \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${|S \cap X| > |Y|}$$\end{document} and there exists a cycle containing Y. This degree sum condition is sharp.
引用
收藏
页码:1077 / 1085
页数:8
相关论文
共 12 条
[1]  
Amar D.(2009)Cyclability in bipartite graphs Opusc. Math. 29 345-364
[2]  
Flandrin E.(1985)Longest cycles in bipartite graphs J. Combin. Theory Ser. B 38 118-131
[3]  
Gancarzewicz G.(1963)On hamiltonian bipartite graphs Isr. J. Math. 1 163-165
[4]  
Jackson B.(2008)A degree sum condition concerning the connectivity and the independence number of a graph Graphs Combin. 24 469-483
[5]  
Moon J.W.(1992)2-neighborhoods and hamiltonian conditions J. Graph Theory 16 267-271
[6]  
Moser L.(1977)Maximale gerade und ungerade Kreise in Graphen. I., Wiss Z. Tech. Hochsch. Ilmenau 23 57-70
[7]  
Ozeki K.(1996)On long cycles in a 2-connected bipartite graph Graphs and Combin. 12 373-384
[8]  
Yamashita T.(undefined)undefined undefined undefined undefined-undefined
[9]  
Shi R.H.(undefined)undefined undefined undefined undefined-undefined
[10]  
Voss H.-J.(undefined)undefined undefined undefined undefined-undefined