On long cycles in a 2-connected bipartite graph (Q2563427)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 957389
Language Label Description Also known as
default for all languages
No label defined
    English
    On long cycles in a 2-connected bipartite graph
    scientific article; zbMATH DE number 957389

      Statements

      On long cycles in a 2-connected bipartite graph (English)
      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
      long cycles
      0 references
      bipartite graphs
      0 references
      cycle
      0 references

      Identifiers