Title

Hamiltonian Spider Intersection Graphs Are Cycle Extendable

Document Type

Article

Publication Date

2013

Publication Source

SIAM Journal on Discrete Mathematics

Abstract

A cycle $C$ in a graph is extendable if there exists a cycle $C'$ such that $V(C) \subseteq V(C')$ and $|V(C')|$ = $|V(C)|$ + 1. A graph is cycle extendable if every non-Hamiltonian cycle in the graph is extendable. An open question is whether or not every Hamiltonian chordal graph is cycle extendable. We show that Hamiltonian spider intersection graphs, a subclass of Hamiltonian chordal graphs, are cycle extendable. Our result generalizes known results on cycle extendability in interval graphs and split graphs.

Inclusive pages

1913–1923

ISBN/ISSN

0895-4801

Comments

Permission documentation on file.

Publisher

Society for Industrial and Applied Mathematics

Volume

27

Issue

4

Peer Reviewed

yes


Share

COinS