Edge condition for long cycles in bipartite graphs
Lech Adamus
Abstract
The following problem was solved by Woodall in 1972: for any pair of
nonnegative integers n
and k<n / 2-1
find
the minimum integer g(n,k) such that every graph with
n
vertices and at least g(n,k) edges contains a cycle of
length
n-k. Woodall proved even more: the size
g(n,k),
in fact, guarantees the existence of cycles Cp
for
all 3≤p ≤n-k. In the paper an analogous
problem
for bipartite graphs is considered. It is proved that every bipartite
graph
with color classes of cardinalities m and n,
m≤n,
and size greater than n(m-k-1)+k+1 contains a cycle of
length 2m-2k,
where m≥1 / 2k2
+ 3 / 2k
+ 4, k∈N. The bound on
the
number of edges is best possible. Moreover, this size condition
guarantees
the existence of cycles of all even lengths up to 2m-2k.
We
also characterize all extremal graphs for this problem. Finally, we
conjecture
that the condition on the order may be relaxed to m≥2k+2.
Full Text: PDF PostScript