Characterizing degree-sum maximal nonhamiltonian bipartite graphs

被引：12

作者：

Ferrara, Michael ^{[1
]}

Jacobson, Michael ^{[1
]}

Powell, Jeffrey ^{[2
]}

机构：

[1] Univ Colorado, Denver, CO 80217 USA

[2] Samford Univ, Birmingham, AL 35229 USA

来源：

DISCRETE MATHEMATICS | 2012年 / 312卷 / 02期

关键词：

Hamiltonian cycle; Bipartite graph;

D O I：

10.1016/j.disc.2011.08.029

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In 1963, Moon and Moser gave a bipartite analogue to Ore's famed theorem on hamiltonian graphs. While the sharpness examples of Ore's Theorem have been independently characterized in at least four different papers, no similar characterization exists for the Moon-Moser Theorem. In this note, we give such a characterization, consisting of one infinite family and two exceptional graphs of order eight. (C) 2011 Elsevier B.V. All rights reserved.

引用

页码：459 / 461

页数：3