Cycle traversability for claw-free graphs and polyhedral maps (Q2216923)

This paper considers the cyclability problem for graphs when certain sets of vertices are to be included and other sets are to be avoided. The authors show that a 3-connected claw-free graph always has a cycle passing through any given five vertices, but avoiding any other one specified vertex. The result is shown to be sharp by exhibiting an infinite family of 3-connected claw-free graphs in which there is no cycle containing a certain set of six vertices but avoiding a seventh specified vertex. The authors also show that a graph polyhedrally embedded in a surface always has a cycle passing through any given three vertices, but avoiding any other specified vertex. The result is shown to be best possible.