On \(k\)-ordered bipartite graphs
The electronic journal of combinatorics, Tome 10 (2003)
In 1997, Ng and Schultz 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.
@article{10_37236_1704,
author = {Jill R. Faudree and Ronald J. Gould and Florian Pfender and Allison Wolf},
title = {On \(k\)-ordered bipartite graphs},
journal = {The electronic journal of combinatorics},
year = {2003},
volume = {10},
doi = {10.37236/1704},
zbl = {1011.05030},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1704/}
}
Jill R. Faudree; Ronald J. Gould; Florian Pfender; Allison Wolf. On \(k\)-ordered bipartite graphs. The electronic journal of combinatorics, Tome 10 (2003). doi: 10.37236/1704
Cité par Sources :