Abstract
Let G[X,Y] be a 2-connected bipartite graph with |X|<|Y|. For S⊆V(G), we define δ(S;G):=min dG(v):v∈S. We define σ1 ,1(G):=min dG(x)+ dG(y):x∈X, y∈Y,xy∉E(G) and σ2(X):=min dG(x)+ dG(y):x,y∈X,x≠y. We denote by c(G) the length of a longest cycle in G. Jackson [B. Jackson, Long cycles in bipartite graphs, J. Combin. Theory Ser. B 38 (1985) 118-131] proved that c(G)<min2δ(X;G) +2δ(Y;G)-2,4δ(X;G)-4,2|Y|. In this paper, we extend this result, and prove that c(G)<min2σ1 ,1(G)-2,2 σ2(X)-4, 2|Y|.
Original language | English |
---|---|
Pages (from-to) | 1857-1862 |
Number of pages | 6 |
Journal | Discrete Mathematics |
Volume | 312 |
Issue number | 11 |
DOIs | |
Publication status | Published - 2012 Jun 6 |
Keywords
- Bipartite graph
- Degree
- Longest cycle
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics