Characterizing degree-sum maximal nonhamiltonian bipartite graphs

M Ferrara; M Jacobson; Jeffrey Powell

doi:10.1016/j.disc.2011.08.029

Characterizing degree-sum maximal nonhamiltonian bipartite graphs

M Ferrara, M Jacobson, Jeffrey Powell

Electronic, Electrical and Systems Engineering

Research output: Contribution to journal › Article

7 Citations (Scopus)

Abstract

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.

Original language	English
Pages (from-to)	459-461
Number of pages	3
Journal	Discrete Mathematics
Volume	312
Issue number	2
DOIs	https://doi.org/10.1016/j.disc.2011.08.029
Publication status	Published - 1 Jan 2012

Keywords

Bipartite graph
Hamiltonian cycle

Access to Document

10.1016/j.disc.2011.08.029

Cite this

@article{dd1fdd597b124cd9862451007472af21,

title = "Characterizing degree-sum maximal nonhamiltonian bipartite graphs",

abstract = "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.",

keywords = "Bipartite graph, Hamiltonian cycle",

author = "M Ferrara and M Jacobson and Jeffrey Powell",

year = "2012",

month = jan,

day = "1",

doi = "10.1016/j.disc.2011.08.029",

language = "English",

volume = "312",

pages = "459--461",

journal = "Discrete Mathematics",

publisher = "Elsevier",

number = "2",

}

TY - JOUR

T1 - Characterizing degree-sum maximal nonhamiltonian bipartite graphs

AU - Ferrara, M

AU - Jacobson, M

AU - Powell, Jeffrey

PY - 2012/1/1

Y1 - 2012/1/1

N2 - 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.

AB - 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.

KW - Bipartite graph

KW - Hamiltonian cycle

U2 - 10.1016/j.disc.2011.08.029

DO - 10.1016/j.disc.2011.08.029

M3 - Article

VL - 312

SP - 459

EP - 461

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 2

ER -

Characterizing degree-sum maximal nonhamiltonian bipartite graphs

Abstract

Keywords

Access to Document

Fingerprint

Cite this