Cycles through subsets with large degree sums
type: Item
instance of: scholarly article
title: Cycles through subsets with large degree sums
zbMATH Open document ID: 0883.05089
DOI: 10.1016/S0012-365X(96)00071-4
author: Hao Li
author: Jianping Li
author: Feng Tian
author: Henk Jan Veldman
author: Hajo Broersma
published in: Discrete Mathematics
publication date: 1997-08-10T00:00:00Z
review text: Let \(G\) be a 2-connected graph on \(n\) vertices and let \(X\subseteq V(G)\). The paper deals with various conditions that ensure that \(G\) has a cycle covering all vertices of \(X\) (in which case \(G\) is \(X\)-cyclable). The conditions are expressed in terms of various parameters related to \(X\). Let \(\alpha(X)\) denote the independence number of the subgraph \(G[X]\) induced by \(X\). If \(G[X]\) is not complete, then \(\kappa(X)\) denotes the minimum cardinality of a set of vertices of \(G\) separating two vertices in \(X\). Denote by \(\delta(X)\) the minimum degree in \(G\) among the vertices in \(X\). Finally, \(\sigma_3(X)\) denotes the minimum value of the degree sum (in \(G\)) of any three pairwise nonadjacent vertices of \(X\). The main results of the paper are: (i) If \(\sigma_3(X)\geq n+\min\{\kappa(X), \delta(X)\}\), then \(G\) is \(X\)-cyclable. (ii) If \(\alpha(X)\leq\kappa(X)\), then \(G\) is \(X\)-cyclable.
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1047078
zbMATH Keywords: Hamiltonian cycle
zbMATH Keywords: connectivity
zbMATH Keywords: \(X\)-cyclable
zbMATH Keywords: independence number
zbMATH Keywords: degree sum
reviewed by: Jørgen Bang-Jensen
MaRDI profile type: Publication
cites work: A generalization of a result of Häggkvist and Nicoghossian
cites work: Long cycles in graphs with large degree sums
cites work: Cycles through specified vertices
cites work: Q4192100
cites work: A method in graph theory
cites work: Q5422499
cites work: Long cycles, degree sums and neighborhood unions
cites work: A note on Hamiltonian circuits
cites work: Some Theorems on Abstract Graphs
cites work: New sufficient conditions for cycles in graphs
cites work: 2‐neighborhoods and hamiltonian conditions
cites work: Cycles containing many vertices of large degree
full work available at URL: s0012-365x(96)00071-4
OpenAlex ID: W1976464549
Recommended article: Cycles through prescribed vertices with large degree sum
Recommended article: Cycles containing many vertices of subsets in graphs with large degree sums and neighborhood unions
Recommended article: Cycles through vertices of large maximum degree
Recommended article: Long cycles in graphs with large degree sums
Recommended article: Cycles containing many vertices of large degree
Recommended article: Q4812923
Recommended article: Cycles containing many vertices of subsets in 1-tough graphs with large degree sums
Recommended article: Long cycles, degree sums and neighborhood unions
Recommended article: Degree Sums and Covering Cycles
Recommended article: Q4862113
description: scientific article; zbMATH DE number 1047078