On stability of the Hamiltonian index under contractions and closures

L. Xiong; Z. Ryjáček; Haitze J. Broersma

On stability of the Hamiltonian index under contractions and closures

L. Xiong, Z. Ryjáček, Haitze J. Broersma

Discrete Mathematics and Mathematical Programming

Research output: Book/Report › Report › Other research output

50 Downloads (Pure)

Abstract

The hamiltonian index of a graph $G$ is the smallest integer $k$ such that the $k$-th iterated line graph of $G$ is hamiltonian. We first show that, with one exceptional case, adding an edge to a graph cannot increase its hamiltonian index. We use this result to prove that neither the contraction of an $A_G(F)$-contractible subgraph $F$ of a graph $G$ nor the closure operation performed on $G$ (if $G$ is claw-free) affects the value of the hamiltonian index of a graph $G$.

Original language	Undefined
Place of Publication	Enschede
Publisher	University of Twente, Department of Applied Mathematics
Publication status	Published - 2002

Publication series

Name	Memorandum
Publisher	Department of Applied Mathematics, University of Twente
No.	1622
ISSN (Print)	0169-2690

Keywords

MSC-05C45
IR-65809
EWI-3442
MSC-05C35

Access to Document

1622
open
Final published version, 226 KB

Cite this

Xiong, L., Ryjáček, Z., & Broersma, H. J. (2002). On stability of the Hamiltonian index under contractions and closures. (Memorandum; No. 1622). Enschede: University of Twente, Department of Applied Mathematics.

@book{312d5c16a8dc40d4b20d2619b0dbc96e,

title = "On stability of the Hamiltonian index under contractions and closures",

abstract = "The hamiltonian index of a graph $G$ is the smallest integer $k$ such that the $k$-th iterated line graph of $G$ is hamiltonian. We first show that, with one exceptional case, adding an edge to a graph cannot increase its hamiltonian index. We use this result to prove that neither the contraction of an $A_G(F)$-contractible subgraph $F$ of a graph $G$ nor the closure operation performed on $G$ (if $G$ is claw-free) affects the value of the hamiltonian index of a graph $G$.",

keywords = "MSC-05C45, IR-65809, EWI-3442, MSC-05C35",

author = "L. Xiong and Z. Ryj{\'a}ček and Broersma, {Haitze J.}",

year = "2002",

language = "Undefined",

series = "Memorandum",

publisher = "University of Twente, Department of Applied Mathematics",

number = "1622",

}

TY - BOOK

T1 - On stability of the Hamiltonian index under contractions and closures

AU - Xiong, L.

AU - Ryjáček, Z.

AU - Broersma, Haitze J.

PY - 2002

Y1 - 2002

N2 - The hamiltonian index of a graph $G$ is the smallest integer $k$ such that the $k$-th iterated line graph of $G$ is hamiltonian. We first show that, with one exceptional case, adding an edge to a graph cannot increase its hamiltonian index. We use this result to prove that neither the contraction of an $A_G(F)$-contractible subgraph $F$ of a graph $G$ nor the closure operation performed on $G$ (if $G$ is claw-free) affects the value of the hamiltonian index of a graph $G$.

AB - The hamiltonian index of a graph $G$ is the smallest integer $k$ such that the $k$-th iterated line graph of $G$ is hamiltonian. We first show that, with one exceptional case, adding an edge to a graph cannot increase its hamiltonian index. We use this result to prove that neither the contraction of an $A_G(F)$-contractible subgraph $F$ of a graph $G$ nor the closure operation performed on $G$ (if $G$ is claw-free) affects the value of the hamiltonian index of a graph $G$.

KW - MSC-05C45

KW - IR-65809

KW - EWI-3442

KW - MSC-05C35

M3 - Report

T3 - Memorandum

BT - On stability of the Hamiltonian index under contractions and closures

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -