Intersection of Longest Cycle and Largest Bond in 3-Connected Graphs
摘要
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.