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 条
  • [21] A note on sum of powers of the Laplacian eigenvalues of bipartite graphs
    Tian, Gui-Xian
    Huang, Ting-Zhu
    Zhou, Bo
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2009, 430 (8-9) : 2503 - 2510
  • [22] Convex bipartite graphs and bipartite circle graphs
    Kizu, T
    Haruta, Y
    Araki, T
    Kashiwabara, T
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 1998, E81A (05) : 789 - 795
  • [23] Extremal bipartite graphs and unicyclic graphs with respect to the eccentric resistance-distance sum
    Li, Shuchao
    Shen, Changlong
    JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS, 2021, 500 (02)
  • [24] Degree sum conditions for Hamiltonicity on κ-partite graphs
    Chen, G
    Jacobson, MS
    GRAPHS AND COMBINATORICS, 1997, 13 (04) : 325 - 343
  • [25] Packing bipartite graphs with covers of complete bipartite graphs
    Chalopin, Jeremie
    Paulusma, Daniel
    DISCRETE APPLIED MATHEMATICS, 2014, 168 : 40 - 50
  • [26] Partial Degree Conditions and Cycle Coverings in Bipartite Graphs
    Suyun Jiang
    Jin Yan
    Graphs and Combinatorics, 2017, 33 : 955 - 967
  • [27] Large bipartite Cayley graphs of given degree and diameter
    Vetrik, Tomas
    Simanjuntak, Rinovia
    Baskoro, Edy Tri
    DISCRETE MATHEMATICS, 2011, 311 (04) : 324 - 326
  • [28] A degree condition of 2-factors in bipartite graphs
    Li, XW
    Wei, B
    Yang, F
    DISCRETE APPLIED MATHEMATICS, 2001, 113 (2-3) : 311 - 318
  • [29] Partial Degree Conditions and Cycle Coverings in Bipartite Graphs
    Jiang, Suyun
    Yan, Jin
    GRAPHS AND COMBINATORICS, 2017, 33 (04) : 955 - 967
  • [30] On sum edge-coloring of regular, bipartite and split graphs
    Petrosyan, P. A.
    Kamalian, R. R.
    DISCRETE APPLIED MATHEMATICS, 2014, 165 : 263 - 269