On long cycles in a 2-connected bipartite graph (Q2563427)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On long cycles in a 2-connected bipartite graph |
scientific article |
Statements
On long cycles in a 2-connected bipartite graph (English)
0 references
22 June 1997
0 references
A result of Bermond states that for a 2-connected graph \(G\) on \(n\) vertices and integer \(k\geq 3\), if \(d(x)+d(y)\geq k\) for every pair of non-adjacent vertices \(x\) and \(y\) of \(G\) then \(G\) contains a cycle of length \(\geq\min(k,n)\). The author shows a similar result for 2-connected bipartite graphs \(G=(A,B;E)\): For \(k\) any integer \(\geq 2\), if \(d(x)+d(y)\geq k+1\) for each pair of non-adjacent vertices \(x\) and \(y\) then \(G\) contains a cycle of length \(\geq\min(2a,2k)\) where \(a=\min(|A|,|B|)\), unless \(G\) is a member of a known family. The author conjectures the result is true when \(|A|=|B|\) and the degree condition is restricted to vertex pairs \(x\), \(y\) with \(x\in A\) and \(y\in B\).
0 references
long cycles
0 references
bipartite graphs
0 references
cycle
0 references