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)]
Improve this question
$\endgroup$
2
  • $\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
    Commented Dec 27, 2013 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
    Commented Jan 5, 2014 at 16:54

1 Answer 1

Reset to default
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
Improve this answer
$\endgroup$
8
  • $\begingroup$ Can you provide the last graph in standard form, please? $\endgroup$
    – Wolfgang
    Commented Jan 5, 2014 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
    Commented Jan 5, 2014 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
    Commented Jan 6, 2014 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
    Commented Jan 6, 2014 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
    Commented Jan 6, 2014 at 10:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .