Cycles through subsets with large degree sums (Q1363686): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claims |
||
Property / author | |||
Property / author: Hajo J. Broersma / rank | |||
Property / reviewed by | |||
Property / reviewed by: Jörgen Bang-Jensen / rank | |||
Revision as of 17:57, 13 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Cycles through subsets with large degree sums |
scientific article |
Statements
Cycles through subsets with large degree sums (English)
0 references
10 August 1997
0 references
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.
0 references
Hamiltonian cycle
0 references
connectivity
0 references
\(X\)-cyclable
0 references
independence number
0 references
degree sum
0 references