5
$\begingroup$

We sometimes say that in a graph $G$ two vertices $a$ and $b$ look the same. In layman's terms, this means that $a$ and $b$ are of same status. Precisely, there exists a auto-isomorphic mapping of $G$ mapping $a$ to $b$.

For example, in the graph below, $u$ and $v$ have the same status, and $x$ and $y$ have the same status.

enter image description here

I have two goals:

  1. Given a vertex of a graph, find all the vertices that have the same status as it.
  2. To divide all vertices of the same status together.

For the first goal, my feeling is that the GraphAutomorphismGroup function can help.

g = Graph[{x <-> u, x <-> v, v <-> y, y <-> u, x <-> y}]
gr = GraphAutomorphismGroup[g]
(* output: PermutationGroup[{Cycles[{{1, 4}}], Cycles[{{2, 3}}]}]*)

From above output of gr, we can sense that some vertices are symmetrical, but the readability is a bit poor.

PS: The advantage of doing that is, for example, if we want to describe if the graph is planar (or whatever it is) if we remove one vertex. Just consider a representation of vertices of the same status. (This saves time when the graph is highly symmetrical.)

$\endgroup$

1 Answer 1

7
$\begingroup$

Your same status means the element is in the same orbit in its automorphism group as Group Theory. And it means there is an element $g$ in its automorphism group such that the image of one point under $g$ is the other point

VertexList[g][[#]]&/@GroupOrbits[gr]

{{x,y},{u,v}}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.