Skip to main content
3 of 8
added 44/109
Wolfgang
  • 13.4k
  • 5
  • 45
  • 102

Graphs with many edges avoided by hamiltonian cycles

Let $G$ be a $3$-connected Hamiltonian graph with at least one edge that belongs to each H-cycle of $G$. Some authors (e.g. in the link given here) call such an edge an a-edge and an edge that belongs to no H-cycle of $G$ a b-edge. Let $a(G)$ and $b(G)$ denote the number of a-edges and b-edges, respectively. Define $\rho(G)=\dfrac{b(G)}{a(G)} $.

  • Are there good (or even sharp) upper bounds for $\rho(G)$ ? Maybe $\rho(G)<1$?

Such graphs can be constructed e.g. using certain non-Hamiltonian graphs like the so-called Tutte fragment $T$ or the “Petersen fragment” $P$, the latter obtained from the Petersen graph by adding a vertex on each of three consecutive edges and an edge leaving at each of those vertices. These edges are labelled by $1,2,3$.

T & P
It is easy to see that $T$ does not admit a H-path between 1 and 3, whereas $P$ admits no H-path starting at 2, only two H-paths between 1 and 3 (one consists of the violet and the red edges, the other one of the violet and the black edges). $T$ has two a-edges (marked in violet) and no b-edges; $P$ has nine a-edges (violet) and three b-edges (light blue).
The simplest $3$-connected Hamiltonian graphs obtained from these are a prism over the big “triangle” of $T$ with $a(G)=3$ and $b(G)=0$ (note that this one is even planar) and likewise a prism over $P$, which has $a(G)=16$ and $b(G)=5$.

By taking a Hamiltonian graph and replacing certain cubic vertices by $T$ or $P$, we can impose restrictions on the H-cycles and obtain graphs with various values of $a(G)$ and $b(G)$.
If we start with the wheel $W_{n}$ and replace one vertice by a $T$ in such a way that the spike becomes an a-edge, the resulting graph has only two H-cycles and $\rho(G)=\dfrac{n-3}{n}$. I wonder if this is best possible. So if generally $\rho(G)<1$ holds, that would be sharp.

What about the maximum if we consider only cubic graphs ?
If we start with the prism over $K_3$ and make one ‘vertical' edge a b-edge by replacing one vertice with a $P$, we get a graph with a unique H-cycle and $\rho(G)=\dfrac{5}{13}\approx.3846 $.
If we start with the dodecahedron and 'block' three well chosen edges (e.g. make them into b-edges) by replacing three vertices with $P$'s, we get a graph with a unique H-cycle and $\rho(G)=\dfrac{16}{41}\approx.3902 $, slightly larger.
Starting with a truncated icosahedron (soccerball), we may possibly still do better. That depends on how many edges have to be blocked by using $P$'s to remain with a unique H-cycle. If there are $k$ such edges and the resulting graph $G$ is unique Hamiltonian, it will have $\rho(G)=\dfrac{30+2k}{60+7k} $, which is equal to $\dfrac{16}{41}$ for $k=9$ and gets bigger as $k$ decreases. I've checked that $k=7$, thus $\rho(G)=\dfrac{44}{109}\approx.4037 $, is possible. (Note that in the drawing given in the link, only the green and black 1-factors yield a H-cycle.)

Of course I don't claim that this method yields the best possible results. So the question:

  • Are there cubic, 3-connected graphs with $\rho(G)$ even bigger than that?
Wolfgang
  • 13.4k
  • 5
  • 45
  • 102