# 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$. 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 'keeps' only two of the H-cycles of $W_n$ and has $\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 (i.e. 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 can still do better. It 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.)

$^*$ Edit: "unique" is meant w.r.t. the H-cycles of the original graph, because inside the instances of $P$ there are of course several ways of making H-paths through them.

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?

The first counterexample given by @joro gives rise to the following family $G_k$ of graphs with $\rho(G_k)=k$ : $G_k$ has $n=4k+3$ vertices numbered $0,1,\dots,n-1$ forming a H-cycle (imagine a regular n-gon embedded such that the vertex $2k+1$ is on the bottom), plus the ‘horizontal’ chords $(2j-1,4k+3-2j)$ for $j=1,...,k$ (call their set $B$) and the other chords $(j,2k+1+j)$ for $j=0,...,2k+1$. It is not hard to see that $(4k+2,0)$ is an a-edge. As the graph without this edge and without $B$ is bipartite, all edges of $B$ must be b-edges. It remains to check that for each other edge, there is a H-cycle that doesn’t contain it.

For the second question, as @Martin Tancer and @nvcleemp have pointed aout, $\rho(G)\le1/2$ for cubic graphs. The following construction comes arbitrarily close to $1/2$ :

For $n=2k$, start with a H-cycle $0,...,2k-1,0$ and add the ‘horizontal’ chords $(j,2k-j)$ for $j=1,...,k-1$ and the ‘vertical’ chord $(0,k)$. Replace the vertex $k$ with an instance of $P$ that blocks the vertical chord. Then it is easy to see (starting at the vertex $0$) that the horizontal chords cannot be part of a H-cycle. So this graph has $a(G)=2k+7$ (the original cycle plus 7 inner edges of $P$) and $b(G)=k+1$ (the horizontal chords plus 2 inner edges of $P$).

So both original questions are answered, thanks to your input. Remains the interesting question raised by joro what can be said about $\rho(G)$ for 4-regular graphs.

• You mean the chords are modulo n? Verified with program for small $k$. – joro Dec 27 '13 at 8:59
• Yes modulo n, but the way I've written it, you don't even need that. I don't have time right now to add a diagram for say k=2 or k=3, but you can easily draw one. For checking that the edges (i,i+1) for i=0,...,n-2 aren't a-edges, it suffices to note that there are 2 H-cycles (symmetric to each other w.r.t. the vertical axis) which alternate essentially between diagonals of the n-gon and edges of it. – Wolfgang Dec 27 '13 at 9:55
• OK. Here is a drawing for k=3: s27.postimg.org/wwx38t3w3/graph_k_3.png – joro Dec 27 '13 at 10:04

The computer found counterexamples to $\rho(G)<1$.

Despite verification, I am not sure this is correct.

$G_1$ on $7$ vertices, $G_2$ on $11$ vertices. $\rho(G_1)=1,\rho(G_2)=2$

$G_1$:

edges=[(0, 3), (0, 4), (0, 5), (1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6), (3, 5), (3, 6), (4, 6)]
A=[(0, 3)]
B=[(4, 6)]


$G_2$:

edges=[(0, 5), (0, 6), (0, 7), (1, 6), (1, 7), (1, 8), (2, 6), (2, 8), (2, 9), (3, 7), (3, 9), (3, 10), (4, 8), (4, 9), (4, 10), (5, 9), (5, 10), (6, 8), (7, 10)]
A=[(0, 5)]
B=[(6, 8), (7, 10)]


Plot of $G_1$: • Thank you. Why should this not be correct? There are interesting patterns in your 2 graphs, which might allow (at least worth a try) to restrict further searches for even higher $\rho(G)$'s: Put $V=V_3\cup V_4$ (vertices of degree 3 and 4). Did you notice that G1 and G2 are "almost bipartite", the vertices of $V_3$ essentially alternating in each H-cycle with those of $V_4$. At the exception of 03 (05 for G2), which is... an a-edge! And the only edges in $\langle V_4\rangle$ are the b-edges. H-cycle e.g. for G1: 0 4 2 6 1 5 3, for G2: 0 6 2 8 1 7 3 9 4 10 5. – Wolfgang Dec 21 '13 at 13:25
• @Wolfgang if you trust my program, there are no cubic counterexamples rho(G) > 1 on less than 20 vertices. – joro Dec 21 '13 at 13:38
• Also note that displaying your $G_1$ and $G_2$ like you would display bipartite graphs, it is almost immediately clear why the a-edges and b-edges are what they are. BTW do you have a feeling that $\rho(G)$ is bounded? – Wolfgang Dec 21 '13 at 13:39
• For cubic ones, I conjecture $rho(G)\le 1/2$. Have you found cubic graphs with bigger rho? – Wolfgang Dec 21 '13 at 13:41
• Isn't $\rho(G) \leq 1/2$ somewhat trivial? A $b$-edge in a cubic graph is incident to four $a$-edges. Each $a$-edge comes this way from at most two $b$-edges. – Martin Tancer Dec 21 '13 at 15:08