Forbidden Subgraphs and Pancyclicity.
Ralph J. Faudree, Ronald J. Gould, Zdeněk Ryjáček, Ingo Schiermeyer · 1995
We prove that every 2--connected K 1;3 -free and Z 3 \\Gammafree graph is hamiltonian except for two graphs. Furthermore, we give a complete characterization of all 2\\Gammaconnected, K 1;3 -free graphs, which are not pancyclic, and which are Z 3 -free, B-free, W -free, or HP 7 \\Gammafree. 1 Research partially supported by ONR grant N00014-91-J-1085 2 Research partially supported by NSA grant MDA 904-90-H-4034 3 Research supported by EC-grant No. 927 1 INTRODUCTION We only consider simple graphs and refer to [BM] for terminology and notation not defined here. A graph G with n 3 vertices is hamiltonian if G contains a cycle of length n and pancyclic if G contains a cycle C k of length k for each k with 3 k n. If Cm is a cycle with m vertices labeled v 1 ; v 2 ; \\Delta \\Delta \\Delta ; v m such that fv i v i+1 j1 i m \\Gamma 1g [ fv m v 1 g ae E(G) and v j v j+k 2 E(G) for some j; k (modulo m), then the edge v j v j+k is called a k--chord of Cm . Clearly, this k\\Gammachord c...