Skip to main content
add proof
Source Link
Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147

If I didn't get my wires crossed, the cartesian product of two transmission-regular graphs is also transmission-regular. This can be used to make examples of arbitrarily high diameter. I'll add a proof tomorrow if nobody finds a counterexample to my claim while I sleep.

ADDED: Let $G, H$ be connected graphs of order $m,n$, respectively. Then in the Cartesian product $G\times H$, we have $d_{G\times H}((u,x),(v,y)) = d_G(u,v)+d_H(x,y)$. From this it is easy to see that the transmission of $(u,x)$ is $n\sigma_u(G) + m\sigma_x(G)$. So $G\times H$ is transmission-regular iff both $G,H$ are.

If I didn't get my wires crossed, the cartesian product of two transmission-regular graphs is also transmission-regular. This can be used to make examples of arbitrarily high diameter. I'll add a proof tomorrow if nobody finds a counterexample to my claim while I sleep.

If I didn't get my wires crossed, the cartesian product of two transmission-regular graphs is also transmission-regular. This can be used to make examples of arbitrarily high diameter. I'll add a proof tomorrow if nobody finds a counterexample to my claim while I sleep.

ADDED: Let $G, H$ be connected graphs of order $m,n$, respectively. Then in the Cartesian product $G\times H$, we have $d_{G\times H}((u,x),(v,y)) = d_G(u,v)+d_H(x,y)$. From this it is easy to see that the transmission of $(u,x)$ is $n\sigma_u(G) + m\sigma_x(G)$. So $G\times H$ is transmission-regular iff both $G,H$ are.

Source Link
Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147

If I didn't get my wires crossed, the cartesian product of two transmission-regular graphs is also transmission-regular. This can be used to make examples of arbitrarily high diameter. I'll add a proof tomorrow if nobody finds a counterexample to my claim while I sleep.