Hamiltonian Spider Intersection Graphs Are Cycle Extendable
SIAM Journal on Discrete Mathematics
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.
Copyright © 2013, Society for Industrial and Applied Mathematics
Society for Industrial and Applied Mathematics
Abueida, Atif; Busch, Arthur; and Sritharan, R., "Hamiltonian Spider Intersection Graphs Are Cycle Extendable" (2013). Computer Science Faculty Publications. 171.