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

MaRDI QIDQ6437798zbMATH OpenFDO

Authors Emily Ren

Publication date 22 May 2023

Mathematics Subject Classification ID

Paths and cycles (05C38) Connectivity (05C40) Eulerian and Hamiltonian graphs (05C45)

Abstract: 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)geqn-3$ or $c^{\ast }(G)geqm-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)$, $1leqk<fracn2$, the co-spectrum of $P(n,k)$ is $3,4,5,\mathrm{...},n+2$.

This page was built for publication: Intersection of Longest Cycle and Largest Bond in 3-Connected Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6437798)