Hamilton-connected indices of graphs

Zhi-Hong Chen, Hong-Jian Lai, Liming Xiong, Huiya Yan, Mingquan Zhan

Research output: Contribution to journalArticlepeer-review

Abstract

Let  G  be an undirected graph that is neither a path nor a cycle. Clark and Wormald [L.H. Clark, N.C. Wormald, Hamiltonian-like indices of graphs, ARS Combinatoria 15 (1983) 131–148] defined  hc(G)  to be the least integer  m  such that the iterated line graph  Lm(G)  is Hamilton-connected. Let  diam(G)  be the diameter of  G  and  k  be the length of a longest path whose internal vertices, if any, have degree 2 in  G . In this paper, we show that  k−1≤hc(G)≤max{diam(G),k−1} . We also show that  κ3(G)≤hc(G)≤κ3(G)+2  where  κ3(G)  is the least integer  m  such that  Lm(G)  is 3-connected. Finally we prove that  hc(G)≤|V(G)|−Δ(G)+1 . These bounds are all sharp.
Original languageAmerican English
JournalDiscrete Mathematics
Volume309
Issue number14
DOIs
StatePublished - Jul 2009

Keywords

  • Connectivity
  • Diameter
  • Hamilton-connected index
  • Iterated line graph
  • Maximum degree

Disciplines

  • Computer Sciences
  • Mathematics

Cite this