The circumference of a graph with no \(K_{3,t}\)-minor (Q859611)

From MaRDI portal





scientific article; zbMATH DE number 5116329
Language Label Description Also known as
default for all languages
No label defined
    English
    The circumference of a graph with no \(K_{3,t}\)-minor
    scientific article; zbMATH DE number 5116329

      Statements

      The circumference of a graph with no \(K_{3,t}\)-minor (English)
      0 references
      0 references
      0 references
      0 references
      0 references
      16 January 2007
      0 references
      Let \(t\) be any integer such that \(t\geq 3\). The authors show that if \(G\) is a 3-connected graph with \(n\) nodes that contains no \(K_{3,t}\)-minors, then \(G\) has a cycle of length at least \(n^{r(t)}\), where \(r(t)= \log_{8t}(t-1)^2\); and if \(G\) is a 2-connected graph with \(n\) nodes that contains no \(K_{2,t}\)-minors, then \(G\) has a cycle of length at least \(n/t^{t-1}\).
      0 references
      cycle
      0 references
      path
      0 references
      connectivity
      0 references
      0 references

      Identifiers