Spanning bipartite graphs with high degree sum in graphs

被引:1
作者
Chen, Guantao [1 ]
Chiba, Shuya [2 ]
Gould, Ronald J. [3 ]
Gu, Xiaofeng [4 ]
Saito, Akira [5 ]
Tsugaki, Masao
Yamashita, Tomoki [6 ]
机构
[1] Georgia State Univ, Dept Math & Stat, Atlanta, GA 30303 USA
[2] Kumamoto Univ, Fac Adv Sci & Technol, Appl Math, 2-39-1 Kurokami, Kumamoto 8608555, Japan
[3] Emory Univ, Dept Math & Comp Sci, Atlanta, GA 30322 USA
[4] Univ West Georgia, Dept Math, Carrollton, GA 30118 USA
[5] Nihon Univ, Dept Informat Sci, Setagaya Ku, Sakurajosui 3-25-40, Tokyo 1568550, Japan
[6] Kindai Univ, Dept Sci, 3-4-1 Kowakae, Higashiosaka, Osaka 5778502, Japan
关键词
Hamiltonian cycle; Ore's Theorem; Bipartite graph;
D O I
10.1016/j.disc.2019.111663
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
The classical Ore's Theorem states that every graph G of order n >= 3 with sigma(2)(G) >= n is hamiltonian, where sigma(2)(G) = min{d(G)(x) + d(G)(y): x, y is an element of V(G), x not equal y, xy is not an element of E(G)}. Recently, Ferrara, Jacobson and Powell (Discrete Math. 312 (2012), 459-461) extended the Moon -Moser Theorem and characterized the non-hamiltonian balanced bipartite graphs H of order 2n >= 4 with partite sets X and Y satisfying sigma(1,1)(H) >= n, where sigma(1.1)(H) = min{d(H)(x)+d(H)(y): x is an element of X, y is an element of Y, xy is not an element of E(H)}. Though the latter result apparently deals with a narrower class of graphs, we prove in this paper that it implies Ore's Theorem for graphs of even order. (C) 2019 Elsevier B.V. All rights reserved.
引用
收藏
页数:8
相关论文
共 50 条
[41]   Complete Graphs and Bipartite Graphs in a Random Graph [J].
Feng, Lijin ;
Barr, Jackson .
2021 5TH INTERNATIONAL CONFERENCE ON VISION, IMAGE AND SIGNAL PROCESSING (ICVISP 2021), 2021, :259-266
[42]   Rainbow and Properly Colored Spanning Trees in Edge-Colored Bipartite Graphs [J].
Mikio Kano ;
Masao Tsugaki .
Graphs and Combinatorics, 2021, 37 :1913-1921
[43]   Rainbow and Properly Colored Spanning Trees in Edge-Colored Bipartite Graphs [J].
Kano, Mikio ;
Tsugaki, Masao .
GRAPHS AND COMBINATORICS, 2021, 37 (05) :1913-1921
[44]   On endotype of bipartite graphs [J].
Li, Weimin .
ARS COMBINATORIA, 2013, 108 :415-424
[45]   On the deficiency of bipartite graphs [J].
Giaro, K ;
Kubale, M ;
Malafiejski, M .
DISCRETE APPLIED MATHEMATICS, 1999, 94 (1-3) :193-203
[46]   Bipartite Graphs and Coverings [J].
Wang, Shiping ;
Zhu, William ;
Min, Fan .
ROUGH SETS AND KNOWLEDGE TECHNOLOGY, 2011, 6954 :722-+
[47]   Generalization of bipartite graphs [J].
Reddy, P. Siva Kota ;
Hemavathi, P. S. .
JOURNAL OF DISCRETE MATHEMATICAL SCIENCES & CRYPTOGRAPHY, 2020, 23 (03) :787-793
[48]   Bipartite covering graphs [J].
Archdeacon, D ;
Kwak, JH ;
Lee, J ;
Sohn, MY .
DISCRETE MATHEMATICS, 2000, 214 (1-3) :51-63
[49]   Equistarable bipartite graphs [J].
Boros, Endre ;
Chiarelli, Nina ;
Milanic, Martin .
DISCRETE MATHEMATICS, 2016, 339 (07) :1960-1969
[50]   On the determinant of bipartite graphs [J].
Bibak, Khodakhast .
DISCRETE MATHEMATICS, 2013, 313 (21) :2446-2450