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

A bond in a graph is a minimal nonempty edge-cut. A connected graph $G$ is dual Hamiltonian if the vertex set can be partitioned into two subsets $X$ and $Y$ such that the subgraphs induced by $X$ and $Y$ are both trees. There is much interest in studying the longest cycles and largest bonds in graphs. H. Wu conjectured that any longest cycle must meet any largest bond in a simple 3-connected graph. In this paper, the author proves that the above conjecture is true for certain classes of 3-connected graphs: Let $G$ be a simple 3-connected graph with $n$ vertices and $m$ edges. Suppose $c(G)$ is the size of a longest cycle, and $c^{\ast }(G)$ is the size of a largest bond. Then each longest cycle meets each largest bond if either $c(G)\ge n-3$ or $c^{\ast }(G)\ge m-n-1$. Sanford determined in her Ph.D. thesis the cycle spectrum of the well-known generalized Petersen graph $P(n,2)$ ($n$ is odd) and $P(n,3)$ ($n$ is even). Flynn proved in her honors thesis that any generalized Petersen graph $P(n,k)$ is dual Hamiltonian. The author studies the bond spectrum (called the co-spectrum) of the generalized Petersen graphs and extends Flynn’s result by proving that in any generalized Petersen graph $P(n,k)$, $1\le k<\frac{n}{2}$, the co-spectrum of $P(n,k)$ is $\{3,4,5,\mathrm{.}\mathrm{.}\mathrm{.},n+2\}$.