Long cycles containing \(k\)-ordered vertices in graphs (Q2477380): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Some Theorems on Abstract Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Onk-ordered graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Degree conditions for <i>k</i>‐ordered hamiltonian graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Onk-ordered Hamiltonian graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A lower bound for the circumference of a graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: k-ordered Hamiltonian graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Note on Hamilton Circuits / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Disjoint paths in graphs. III: Characterization / rank | |||
Normal rank |
Latest revision as of 19:25, 27 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Long cycles containing \(k\)-ordered vertices in graphs |
scientific article |
Statements
Long cycles containing \(k\)-ordered vertices in graphs (English)
0 references
13 March 2008
0 references
A graph \(G\) on \(n\) vertices is said to be \(k\)-ordered hamiltonian for \(2\leq k\leq n\), if for every ordered set \(S\) of \(k\) distinct vertices, there is a cycle in \(G\) containing all of the vertices of \(S\) in the designated order. This concept was introduced by Chartrand but first used by Ng and Schulz. In this paper, the authors, establish the following result. Theorem. Let \(G\) be a \((k+2)\)-connected graph on \(n\) vertices and let \(S\) be an ordered set of \(k\) vertices. If there is is a cycle in \(G\) containing all of the vertices of \(S\) in the designated order, then there is such a cycle of length at least \(\min \{n,\sigma_2(G)\}\). This result qeneralizes several related results.
0 references
\(k\)-ordered graph
0 references
longest cycle
0 references
circumference bound
0 references
noninsertible vertex
0 references