Cycles through specified vertices (Q684399): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
| Property / cites work | |||
| Property / cites work: The longest cycle of a graph with a large minimal degree / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Some Theorems on Abstract Graphs / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: The longest cycles in a graph G with minimum degree at least \(| G| /k\) / rank | |||
Normal rank | |||
Latest revision as of 09:25, 22 May 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Cycles through specified vertices |
scientific article |
Statements
Cycles through specified vertices (English)
0 references
15 September 1993
0 references
The authors relax a minimum degree condition on a graph which guarantees long cycles and consider a set \(W\) of vertices with degree at least \(d\geq 1\), in a graph \(G\) with \(n\) vertices in total. Without imposing any further conditions on \(G\), it is shown that there is a cycle in \(G\) containing at least \(\bigl\lceil{| W|\over\lceil n/d\rceil- 1}\bigr\rceil\) vertices in \(W\). Extremal graphs are produced to show that the result is best possible.
0 references
extremal graphs
0 references
long cycles
0 references
