A symmetry related to rooted products of simple graphs?

57 Views Asked by At

For some simple graphs when multiplied with rooted multiplication, the choice of node to mark as the root doesn't effect the result. Examples include:

The zero, one and two node graphs.

Cycles

Fully connected graphs.

These graphs seem clearly symmetrical, but is there a name for this sort of symmetry?


The meaning of rooted product: https://en.m.wikipedia.org/wiki/Rooted_product_of_graphs

Wiki also lists various symmetry like constraints such as zero-symmetric, semi-symmetric, and distance-transitive, however I'm still not sure.

1

There are 1 best solutions below

3
On BEST ANSWER

It sounds like the property that you are looking for is vertex-transitive. We say that a graph $G$ is vertex transitive if for any two vertices $u$ and $v$, there exists an automorphism on $G$ (that is, an isomorphism of $G$ onto itself) that takes $u$ to $v$. In a vague sense, vertex transitivity means that no vertex of $G$ is special, that the graph looks the same from any vertex. Examples contain the graphs you stated: cycles, complete graphs, the petersen graph, etc.

If you take a rooted product of $G$ with $H$, where $H$ is vertex transitive, then it doesn't matter what you choose the root of $H$ to be, since "no vertex of $H$ is special." There may be particular cases of $G$ and $H$ where the choice of the root doesn't matter, but this would be highly dependent on the structures of $G$ and $H$. By and large, it seems, $H$ would have to be vertex transitive for the choice of the root to not affect the result of the rooted product.