Cycles through prescribed vertices with large degree sum (Q1901041): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Long cycles in graphs with large degree sums / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5722820 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Note on Hamilton Circuits / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: 2‐neighborhoods and hamiltonian conditions / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0012-365x(94)00036-i / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2151291961 / rank | |||
Normal rank |
Latest revision as of 11:26, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Cycles through prescribed vertices with large degree sum |
scientific article |
Statements
Cycles through prescribed vertices with large degree sum (English)
0 references
30 May 1996
0 references
Let \(G\) be a graph with vertex set \(V\) and let \(S\) be a set of vertices in \(G\). For vertices \(u\) and \(v\) of \(G\) define \(\kappa(u, v; G)\) to be the maximum number of disjoint paths from \(u\) to \(v\) in \(G\) and let \(\kappa(S; G)= \min\{\kappa(u, v; G)\mid u, v\in S\) and \(u\neq v\}\). Suppose \(S\) satisfies \(\kappa(S; G)\geq k\geq 2\). Denote by \(\sigma_{k+ 1}(S; G)\) the smallest degree sum of \(k+ 1\) independent vertices in \(S\). The author produces sharp lower bounds for \(\sigma_{k+ 1}(S; G)\) in terms of \(|V|\), \(k\) and the independence number of the induced subgraph \(G[S]\) to ensure that \(G\) has a cycle containing all vertices of \(S\). In particular, if \(G\) is \(k\)-connected, he gives bounds on \(\sigma_{k+ 1}(V; G)\) which guarantee that there is a Hamiltonian cycle.
0 references
paths
0 references
bounds
0 references
independence number
0 references
cycle
0 references
Hamiltonian cycle
0 references