A bond in a graph is a minimal non-empty edge-cut. Suppose G be a graph with n vertices and m edges. Let \(c(G)\) be the number of edges in the longest cycle and let \(c^*(G)\) be the number of edges in the largest bond. Then \(c(G)\le n\) and \(c^*(G)\le m - n\) + 2. Wu conjectured that in a simple 3-connected graph, every longest cycle meets every largest bond. In this paper, the author makes progress toward this conjecture. The main theorem proves the conjecture for \(c(G)\ge n - 3\) or \(c^*(G)\ge m - n - 1\) . The author also proves that the generalized Petersen graph \(P(n, k)\) \((1\le k\ < \frac {n}{2})\) has bonds of all sizes, thereby extending a result by Flynn who proved that the generalized Petersen graph \(P(n, k)\) ( \(1\le k\ < \frac {n}{2}\) ) has a bond of maximum size n + 2.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Intersection of Longest Cycle and Largest Bond in 3-Connected Graphs

  • Emily Ren

摘要

A bond in a graph is a minimal non-empty edge-cut. Suppose G be a graph with n vertices and m edges. Let \(c(G)\) be the number of edges in the longest cycle and let \(c^*(G)\) be the number of edges in the largest bond. Then \(c(G)\le n\) and \(c^*(G)\le m - n\) + 2. Wu conjectured that in a simple 3-connected graph, every longest cycle meets every largest bond. In this paper, the author makes progress toward this conjecture. The main theorem proves the conjecture for \(c(G)\ge n - 3\) or \(c^*(G)\ge m - n - 1\) . The author also proves that the generalized Petersen graph \(P(n, k)\) \((1\le k\ < \frac {n}{2})\) has bonds of all sizes, thereby extending a result by Flynn who proved that the generalized Petersen graph \(P(n, k)\) ( \(1\le k\ < \frac {n}{2}\) ) has a bond of maximum size n + 2.