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 条
  • [31] On sum edge-coloring of regular, bipartite and split graphs
    Petrosyan, P. A.
    Kamalian, R. R.
    DISCRETE APPLIED MATHEMATICS, 2014, 165 : 263 - 269
  • [32] On the sum of the squares of all distances in bipartite graphs with given connectivity
    Geng, Xianya
    Zhao, Hongjin
    DISCRETE APPLIED MATHEMATICS, 2018, 239 : 206 - 212
  • [33] The number of spanning trees in Km,n-complements of bipartite graphs
    Gong, Helin
    Yan, Xiurong
    Li, Anshui
    DISCRETE APPLIED MATHEMATICS, 2025, 367 : 40 - 52
  • [34] Spanning trees of bipartite graphs with a bounded number of leaves and branch vertices
    Huang, Xinyu
    Yan, Zheng
    DISCRETE APPLIED MATHEMATICS, 2025, 363 : 105 - 109
  • [35] On the hyperbolicity of bipartite graphs and intersection graphs
    Coudert, David
    Ducoffe, Guillaume
    DISCRETE APPLIED MATHEMATICS, 2016, 214 : 187 - 195
  • [36] Hamiltonian cycles in bipartite toroidal graphs with a partite set of degree four vertices
    Fujisawa, Jun
    Nakamoto, Atsuhiro
    Ozeki, Kenta
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2013, 103 (01) : 46 - 60
  • [37] Weakly bipancyclic bipartite graphs
    Hu, Zhiquan
    Sun, Jing
    DISCRETE APPLIED MATHEMATICS, 2015, 194 : 102 - 120
  • [38] Maximum values of degree-based entropies of bipartite graphs
    Dong, Yanni
    Qiao, Shengning
    Chen, Bing
    Wan, Pengfei
    Zhang, Shenggui
    APPLIED MATHEMATICS AND COMPUTATION, 2021, 401
  • [39] Bipartite-threshold graphs and lifting rotations of edges in bipartite graphs
    Baranskii, V. A.
    Sen'chonok, T. A.
    TRUDY INSTITUTA MATEMATIKI I MEKHANIKI URO RAN, 2023, 29 (01): : 24 - 35
  • [40] On the minimum eccentric distance sum of bipartite graphs with some given parameters
    Li, S. C.
    Wu, Y. Y.
    Sun, L. L.
    JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS, 2015, 430 (02) : 1149 - 1162