AMS Subject Classification (1991) Classes: 05C38, 05C70, 05C35
Springer Online Journal Archives 1860-2000
G =(V,E) is a 2-connected graph, and X is a set of vertices of G such that for every pair x,x' in X, , and the minimum degree of the induced graph 〈X〉 is at least 3, then X is covered by one cycle. This result will be in fact generalised by considering tuples instead of pairs of vertices. Let be the minimum degree in the induced graph 〈X〉. For any , . If , and , then X is covered by at most (p-1) cycles of G. If furthermore , (p-1) cycles are sufficient. So we deduce the following: Let p and t ( ) be two integers. Let G be a 2-connected graph of order n, of minimum degree at least t. If , and , then V is covered by at most cycles, where k is the connectivity of G. If furthermore , (p-1) cycles are sufficient. In particular, if and , then G is hamiltonian.
Type of Medium: