The hamiltonian index of a 2-connected graph

Liming Xiong*, Qiuxin Wu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)

Abstract

Let G be a graph. Then the hamiltonian index h (G) of G is the smallest number of iterations of line graph operator that yield a hamiltonian graph. In this paper we show that h (G) ≤ max {1, frac(| V (G) | - Δ (G), 3)} for every 2-connected simple graph G that is not isomorphic to the graph obtained from a dipole with three parallel edges by replacing every edge by a path of length l ≥ 3. We also show that max {h (G), h (over(G, -))} ≤ frac(| V (G) | - 3, 6) for any two 2-connected nonhamiltonian graphs G and over(G, -) with at least 74 vertices. The upper bounds are all sharp.

Original languageEnglish
Pages (from-to)6373-6382
Number of pages10
JournalDiscrete Mathematics
Volume308
Issue number24
DOIs
Publication statusPublished - 28 Dec 2008

Keywords

  • Complement graph
  • Connectivity
  • Hamiltonian index
  • Maximum degree

Fingerprint

Dive into the research topics of 'The hamiltonian index of a 2-connected graph'. Together they form a unique fingerprint.

Cite this