Skip to main content
replaced http://mathoverflow.net/ with https://mathoverflow.net/
Source Link

Special case of this questionthis 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)]

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)]

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)]
Source Link
joro
  • 25.4k
  • 10
  • 66
  • 121

Regular graphs with $a$ and $b$ Hamiltonian edges

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)]