A generalization of Dirac's theorem on cycles through k vertices in k-connected graphs

作者：Flandrin Evelyne^*; Li Hao; Marczyk Antoni; Wozniak Mariusz

来源：Discrete Mathematics, 2007, 307(7-8): 878-884.

DOI：10.1016/j.disc.2005.11.052

• graphs
• cycles
• Hamiltonian graphs
• cyclability

Let X be a subset of the vertex set of a graph G. We denote by K(X) the smallest number of vertices separating two vertices of X if X does not induce a complete subgraph of G, otherwise we put kappa(X) = vertical bar X vertical bar - 1 if vertical bar X vertical bar >= 2 and K(X) = 1 if vertical bar X vertical bar = 1. We prove that if kappa(X) >= 2 then every set of at most kappa(X) vertices of X is contained in a cycle of G. Thus, we generalize a similar result of Dirac. Applying this theorem we improve our previous result involving an Ore-type condition and give another proof of a slightly improved version of a theorem of Broersma et al.

• 出版日期2007-4-6