Long cycles in bipartite graphs |
| |
Authors: | Bill Jackson |
| |
Institution: | Department of Mathematics, Goldsmiths'' College, London SE14 6NW, England |
| |
Abstract: | Let G be a 2-connected bipartite graph with bipartition (A, B), where |A| ≥ |B|. It is shown that if each vertex of A has degree at least k, and each vertex of B has degree at least l, then G contains a cycle of length at least 2min(|B|, k + l ? 1, 2k ? 2). Then this result is used to determine the minimum number of edges required in a bipartite graph to ensure a cycle of length at least 2m, for any integer m ≥ 2. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|