Neighborhoods and Covering Vertices by Cycles |
| |
Authors: | Mekkia Kouider |
| |
Institution: | (1) L.R.I., U R A 410 C.N.R.S. Bat. 490, Université Paris-Sud; 91405 Orsay Cedex, France; E-mail: km@lri.fr, FR |
| |
Abstract: | 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.
Received April 3, 1998 |
| |
Keywords: | AMS Subject Classification (1991) Classes: 05C38 05C70 05C35 |
本文献已被 SpringerLink 等数据库收录! |
|