On \(k\)-ordered bipartite graphs (Q1871375): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Latest revision as of 06:00, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On \(k\)-ordered bipartite graphs |
scientific article |
Statements
On \(k\)-ordered bipartite graphs (English)
0 references
7 May 2003
0 references
Summary: In 1997, \textit{L. Ng} and \textit{M. Schultz} [J. Graph Theory 24, 45-57 (1997; Zbl 0864.05062)] introduced the idea of cycle orderability. For a positive integer \(k\), a graph \(G\) is \(k\)-ordered if for every ordered sequence of \(k\) vertices, there is a cycle that encounters the vertices of the sequence in the given order. If the cycle is also a Hamiltonian cycle, then \(G\) is said to be \(k\)-ordered Hamiltonian. We give minimum degree conditions and sum of degree conditions for nonadjacent vertices that imply a balanced bipartite graph to be \(k\)-ordered Hamiltonian. For example, let \(G\) be a balanced bipartite graph on \(2n\) vertices, \(n\) sufficiently large. We show that for any positive integer \(k\), if the minimum degree of \(G\) is at least \((2n+k-1)/4\), then \(G\) is \(k\)-ordered Hamiltonian.
0 references
\(k\)-ordered Hamiltonian
0 references