3
$\begingroup$

Special case of this question.

Let $G$ be $r$-regular Hamiltonian graph.

An $a$ edge is an edge which is on every Hamiltonian cycle. A $b$ edge is an edge which is on no Hamiltonian cycle. $a(G)$ and $b(G)$ are numbers of $a$ and $b$ edges.

Assume $a(G)>0$.

Define $ \rho(G)=\dfrac{b(G)}{a(G)}$.

What are upper bounds for $\rho(G)$?


Partial results.

The linked question showed for cubic graphs $\rho(G) \le \frac12$.

For $4$-regular graphs search by nvcleemp showed the largest $\rho(G)$ on up to $14$ vertices is $1$ other being $\frac12,\frac13$.

What about $4$-regular graphs? Is $1$ upper bound?

This might show uniquely Hamiltonian $r$-regular graphs don't exist.

An example of $4$-regular with $\rho(G)=1$ (maybe the smallest) is:

 [(0, 4), (0, 6), (0, 8), (0, 9), (1, 5), (1, 7), (1, 10), (1, 11), (2, 6), (2, 8), (2, 9), (2, 10), (3, 7), (3, 9), (3, 10), (3, 11), (4, 6), (4, 8), (4, 9), (5, 7), (5, 10), (5, 11), (6, 8), (7, 11)]
$\endgroup$
  • $\begingroup$ Just as a confirmation: there is exactly one 4-regular graph $G$ on 12 vertices with $\rho(G)=1$. No 4-regular graphs on less vertices has $\rho$ equal to 1. $\endgroup$ – nvcleemp Dec 27 '13 at 14:41
  • $\begingroup$ I see you dropped the 3-connectedness. Your example is only 2-connected. Take the H-cycle 1 5 7 11 3 9 0 4 8 6 2 10 and you'll see that (2,9) or (3,10) are cutting edges. I haven't checked the connectedness of your gadgets below, though. $\endgroup$ – Wolfgang Jan 5 '14 at 16:54
2
$\begingroup$

There are infinite families of $4$ and $5$ regular graphs with $\rho(G)=1$ using a gadget.

A gadget is graph $GA$ with $2$ vertices $u,v$ of degree $d-1$ and the rest are of degree $d$. The gadget contains sufficiently many $b'$ edges which are no $uv$ Hamiltonian path compared to $a'$ edges which are on all H-$uv$ paths.

Take $n$ copies of $GA$ connect the $u,v$ edges in cycles.

An example a $GA_5$ whith one $b'$ edge and no $a'$ edges is:

GA_5=[(0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (2, 3), (2, 4), (2, 5), (2, 6), (3, 6), (3, 7), (4, 6), (4, 7), (5, 7)]
b'=(2,5)

The $5$-regular graph of two $GA_5$.

[(0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (2, 3), (2, 4), (2, 5), (2, 6), (2, 13), (3, 6), (3, 7), (4, 6), (4, 7), (5, 7), (5, 10), (8, 11), (8, 12), (8, 13), (8, 14), (8, 15), (9, 11), (9, 12), (9, 13), (9, 14), (9, 15), (10, 11), (10, 12), (10, 13), (10, 14), (11, 14), (11, 15), (12, 14), (12, 15), (13, 15)]

For $4$-regular $\rho(G)=2$ is possible using a similar gadget.

graph6 string:

 W?`DDD[VBgPW????A?@????_?@??D??DC?@[??V??Bg??PW
$\endgroup$
  • $\begingroup$ Can you provide the last graph in standard form, please? $\endgroup$ – Wolfgang Jan 5 '14 at 16:55
  • $\begingroup$ Also I try to understand your $GA_5$. Take the H-cycle 073164250 as octogon with 52 on top, then the graph has a vertical axis of symmetry. The H-cycles 036175240 and 074623150 + their reflected ones show that there are no a and b edges. So there are no $a'$ and $b'$ edges either. ??? $\endgroup$ – Wolfgang Jan 5 '14 at 21:17
  • $\begingroup$ @Wolfgang I dropped 3-connectivity indeed. RE: gadget. I believe nvcleemp verified the graphs. The gadget works with $u,v$ H-paths, not with H-cycles. The gadget has 2 additional edges to the low degree vertices, one enters it and one leaves. Necessary condition for a cycle is a H-path in the gadget. The edges of the graph soon. $\endgroup$ – joro Jan 6 '14 at 5:58
  • $\begingroup$ @Wolfgang The last graph with rho=2: [(0, 4), (0, 6), (0, 7), (0, 11), (1, 5), (1, 8), (1, 9), (1, 10), (2, 6), (2, 7), (2, 10), (2, 15), (3, 8), (3, 9), (3, 10), (3, 14), (4, 8), (4, 9), (4, 11), (5, 8), (5, 9), (5, 10), (6, 7), (6, 11), (7, 11), (12, 16), (12, 18), (12, 19), (12, 23), (13, 17), (13, 20), (13, 21), (13, 22), (14, 18), (14, 19), (14, 22), (15, 20), (15, 21), (15, 22), (16, 20), (16, 21), (16, 23), (17, 20), (17, 21), (17, 22), (18, 19), (18, 23), (19, 23)] $\endgroup$ – joro Jan 6 '14 at 6:05
  • $\begingroup$ RE: gadget. I understand the uv H-paths (equivalently H-cycles containing the edge uv=52). But I have a hard time finding your "sufficiently many b′ edges". As far as I see, each edge occurs in some uv H-path. The only b edges in the construction may be the uv of each gadget. Is that what you mean? RE: last graph. Thank you. For 2-connected graphs it is indeed easy to guarantee a-edges. BTW I think similar constructions taking as gadget the Meredith graph with one or two edges removed should also work and have higher connectivity, but it is somewhat messy to check by hand. $\endgroup$ – Wolfgang Jan 6 '14 at 10:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.