TY - JOUR

T1 - Cycles through subsets with large degree sums

AU - Broersma, Haitze J.

AU - Li, Hao

AU - Li, Jianping

AU - Tian, Feng

AU - Veldman, H.J.

PY - 1997

Y1 - 1997

N2 - Let G be a 2-connected graph on n vertices and let X V(G). We say that G is X-cyclable if G has an X-cycle, i.e., a cycle containing all vertices of X. We denote by ¿(X) the maximum number of pairwise nonadjacent vertices in the subgraph G[X] of G induced by X. If G[X] is not complete, we denote by ¿(X) the minimum cardinality of a set of vertices of G separating two vertices of X. By ¿(X) we denote the minimum degree (in G) of the vertices of X, and by ¿3(X) the minimum value of the degree sum (in G) of any three pairwise nonadjacent vertices of X. Our first main result is the following extension in terms of X-cyclability of a result on hamiltonian graphs by Bauer et al. If ¿3(X) n + mingk(X), ¿(X), then G is X-cyclable. Our second main result is the following generalization of a result of Fournier. If ¿(X) ¿(X), then G is X-cyclable. We give a number of extensions of other known results, thereby generalizing some recent results of Veldman.

AB - Let G be a 2-connected graph on n vertices and let X V(G). We say that G is X-cyclable if G has an X-cycle, i.e., a cycle containing all vertices of X. We denote by ¿(X) the maximum number of pairwise nonadjacent vertices in the subgraph G[X] of G induced by X. If G[X] is not complete, we denote by ¿(X) the minimum cardinality of a set of vertices of G separating two vertices of X. By ¿(X) we denote the minimum degree (in G) of the vertices of X, and by ¿3(X) the minimum value of the degree sum (in G) of any three pairwise nonadjacent vertices of X. Our first main result is the following extension in terms of X-cyclability of a result on hamiltonian graphs by Bauer et al. If ¿3(X) n + mingk(X), ¿(X), then G is X-cyclable. Our second main result is the following generalization of a result of Fournier. If ¿(X) ¿(X), then G is X-cyclable. We give a number of extensions of other known results, thereby generalizing some recent results of Veldman.

U2 - 10.1016/S0012-365X(96)00071-4

DO - 10.1016/S0012-365X(96)00071-4

M3 - Article

VL - 171

SP - 43

EP - 54

JO - Discrete mathematics

JF - Discrete mathematics

SN - 0012-365X

ER -