Hamiltonian Spider Intersection Graphs Are Cycle Extendable

Author(s)

Atif Abueida, University of DaytonFollow
Arthur Busch, University of DaytonFollow
R. Sritharan, University of DaytonFollow

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.

Copyright

Copyright © 2013, Society for Industrial and Applied Mathematics

Publisher

Society for Industrial and Applied Mathematics

Volume

27

Peer Reviewed

yes

Issue

4

eCommons Citation

Abueida, Atif; Busch, Arthur; and Sritharan, R., "Hamiltonian Spider Intersection Graphs Are Cycle Extendable" (2013). Computer Science Faculty Publications. 171.
https://ecommons.udayton.edu/cps_fac_pub/171