Cycles through subsets with large degree sums
Broersma, Hajo and Li, Hao and Li, Jianping and Tian, Feng and Veldman, Henk Jan (1997) Cycles through subsets with large degree sums. Discrete Mathematics, 171 (13). pp. 4354. ISSN 0012365X

PDF
596kB 
Abstract:  Let G be a 2connected graph on n vertices and let X V(G). We say that G is Xcyclable if G has an Xcycle, 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 Xcyclability of a result on hamiltonian graphs by Bauer et al. If ¿3(X) n + mingk(X), ¿(X), then G is Xcyclable. Our second main result is the following generalization of a result of Fournier. If ¿(X) ¿(X), then G is Xcyclable. We give a number of extensions of other known results, thereby generalizing some recent results of Veldman. 
Item Type:  Article 
Copyright:  © 1997 Elsevier Science 
Faculty:  Electrical Engineering, Mathematics and Computer Science (EEMCS) 
Research Group:  
Link to this item:  http://purl.utwente.nl/publications/30142 
Official URL:  http://dx.doi.org/10.1016/S0012365X(96)000714 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page
Metis ID: 140781