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
    0 references
    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
    0 references
    long cycles
    0 references
    bipartite graphs
    0 references
    cycle
    0 references