Spanning Bipartite Graphs with Large Degree Sum in Graphs of Odd Order
Spanning Bipartite Graphs with Large Degree Sum in Graphs of Odd Order
复制标题
奇数阶图中具有大度和的生成二部图
DOI：
10.1007/s00373-021-02349-y
复制
发表时间：
2021
影响因子：
0.7
通讯作者：
Yamashita Tomoki
中科院分区：
文献类型：
--
作者：
Chiba Shuya;Saito Akira;Tsugaki Masao;Yamashita Tomoki
For a graphG, defineby \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sigma _2(G)=\min \bigl \{d_G(x)+d_G(y):x, y\in V(G), x\ne y, xy\notin E(G)\bigr \}$$\end{document}. IfGis a bipartite graph with partite setsXandY, we also defineby σ1,1(G)=min{dG(x)+dG(y):x∈X,y∈Y,xy∉E(G)}. Ore’s theorem states that a graph of orderwithcontains a hamiltonian cycle and the Moon–Moser theorem states that a balanced bipartite graphGof orderwithcontains a hamiltonian cycle. In Chen et al. (Discrete Math 343:Article No. 111663, 2020), we studied the relationship between Ore’s theorem and the Moon–Moser theorem, and proved that the refinement of the Moon–Moser theorem given by Ferrara et al. (Discrete Math 312:459–461, 2012) implies Ore’s theorem for graphs of even order. In this paper, we extend the above study to the graphs of odd order. Since no graphs of odd order contain a spanning balanced bipartite subgraph, the Moon–Moser theorem does not work in this case. We instead introduce its counterpart for the graphs in which the orders of the partite sets differ by 1, proved in Matsubara et al. (Discrete Math 340:87–95, 2017). We refine this result and prove that this refinement implies Ore’s theorem.
For a graphG, defineby \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sigma _2(G)=\min \bigl \{d_G(x)+d_G(y):x, y\in V(G), x\ne y, xy\notin E(G)\bigr \}$$\end{document}. IfGis a bipartite graph with partite setsXandY, we also defineby σ1,1(G)=min{dG(x)+dG(y):x∈X,y∈Y,xy∉E(G)}. Ore’s theorem states that a graph of orderwithcontains a hamiltonian cycle and the Moon–Moser theorem states that a balanced bipartite graphGof orderwithcontains a hamiltonian cycle. In Chen et al. (Discrete Math 343:Article No. 111663, 2020), we studied the relationship between Ore’s theorem and the Moon–Moser theorem, and proved that the refinement of the Moon–Moser theorem given by Ferrara et al. (Discrete Math 312:459–461, 2012) implies Ore’s theorem for graphs of even order. In this paper, we extend the above study to the graphs of odd order. Since no graphs of odd order contain a spanning balanced bipartite subgraph, the Moon–Moser theorem does not work in this case. We instead introduce its counterpart for the graphs in which the orders of the partite sets differ by 1, proved in Matsubara et al. (Discrete Math 340:87–95, 2017). We refine this result and prove that this refinement implies Ore’s theorem.
影响因子：
0.8
作者：
M. Ferrara;M. Jacobson;Jeffrey S. Powell
通讯作者：
Jeffrey S. Powell