Hamiltonian Cycles in Critical Graphs with Large Maximum Degree

详细信息    查看全文

• 作者：Rong Luo ; Zhengke Miao ; Yue Zhao
• 关键词：Edge colorings ; Critical graphs ; Hamiltonian cycles
• 刊名：Graphs and Combinatorics
• 出版年：2016
• 出版时间：September 2016
• 年：2016
• 卷：32
• 期：5
• 页码：2019-2028
• 全文大小：404 KB
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Engineering Design
  
• 出版者：Springer Japan
• ISSN：1435-5914
• 卷排序：32

文摘

It is shown by Luo and Zhao (J Graph Theory 73:469–482, 2013) that an overfull \(\Delta \)-critical graph with n vertices that satisfies \(\Delta \ge \frac{n}{2}\) is Hamiltonian. If Hilton’s overfull subgraph conjecture (Chetwynd and Hilton 100:303–317, 1986) was proved to be true, then the above result could be said that any \(\Delta \)-critical graph with n vertices that satisfies \(\Delta \ge \frac{n}{2}\) is Hamiltonian. Since the overfull subgraph conjecture is still open, the natural question is how to directly prove a \(\Delta \)-critical graph with n vertices that satisfies \(\Delta \ge \frac{n}{2}\) is Hamiltonian. Luo and Zhao (J Graph Theory 73:469–482, 2013) show that a \(\Delta \)-critical graph with n vertices that satisfies \(\Delta \ge \frac{6n}{7}\) is Hamiltonian. In this paper, by developing new lemmas for critical graphs, we show that if G is a \(\Delta \)-critical graph with n vertices satisfying \(\Delta \ge \frac{4n}{5}\), then G is Hamiltonian.