On Cycle- and Bi-cycle Extendability in Chordal and Chordal Bipartite Graphs

摘要

A graph (bipartite graph) is chordal (chordal bipartite) if the largest induced cycle is of length three (four); i.e., if every cycle large enough to have a chord does have a chord. In a graph (bipartite graph), a cycle C of length k is extendable (bi-extendable) if there is a cycle C~* on k + 1 (k + 2) vertices with V(C) is contained in V(C~*). A graph (bipartite graph) is called cycle extendable (bi-cycle extendable) if every non-hamiltonian cycle is extendable (bi-extendable). We investigate whether hamiltonian chordal graphs are cycle extendable, and whether chordal bipartite graphs are bi-cycle extendable.