Hamiltonian Cycles In Critical Graphs With Large Maximum Degree

Keywords

Critical graphs; Edge colorings; Hamiltonian cycles

Abstract

It is shown by Luo and Zhao (J Graph Theory 73:469–482, 2013) that an overfull Δ -critical graph with n vertices that satisfies Δ≥n2 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 Δ -critical graph with n vertices that satisfies Δ≥n2 is Hamiltonian. Since the overfull subgraph conjecture is still open, the natural question is how to directly prove a Δ -critical graph with n vertices that satisfies Δ≥n2 is Hamiltonian. Luo and Zhao (J Graph Theory 73:469–482, 2013) show that a Δ -critical graph with n vertices that satisfies Δ≥6n7 is Hamiltonian. In this paper, by developing new lemmas for critical graphs, we show that if G is a Δ -critical graph with n vertices satisfying Δ≥4n5, then G is Hamiltonian.

Publication Date

9-1-2016

Publication Title

Graphs and Combinatorics

Volume

32

Issue

5

Number of Pages

2019-2028

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1007/s00373-016-1698-7

Socpus ID

84962140692 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84962140692

This document is currently not available here.

Share

COinS