Skip to main content
corrected a couple instances of 'vertice' to 'vertex'
Source Link

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 verticevertex 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 verticevertex 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.)

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

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 vertex 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 vertex 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.)

replaced http://math.stackexchange.com/ with https://math.stackexchange.com/
Source Link

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 herehere) 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)} $.

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)} $.

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)} $.

added correction concerning the mention of "unique" H-cycles
Source Link
Wolfgang
  • 13.4k
  • 5
  • 45
  • 102

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.

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 $\rho(G)=\dfrac{n-3}{n}$. I wonder if this is best possible. So if generally $\rho(G)<1$ holds, that would be sharp.

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.

added correction concerning the mention of "unique" H-cycles
Source Link
Wolfgang
  • 13.4k
  • 5
  • 45
  • 102
Loading
deleted 11 characters in body; edited title
Source Link
Wolfgang
  • 13.4k
  • 5
  • 45
  • 102
Loading
added 44/109
Source Link
Wolfgang
  • 13.4k
  • 5
  • 45
  • 102
Loading
formatting
Source Link
Wolfgang
  • 13.4k
  • 5
  • 45
  • 102
Loading
Source Link
Wolfgang
  • 13.4k
  • 5
  • 45
  • 102
Loading