Skip to main content
Added rho=2
Source Link
joro
  • 25.4k
  • 10
  • 66
  • 121

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

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

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

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