Skip to main content
MathOverflow

Return to Answer

added 247 characters in body
Source Link
Jukka Kohonen
Jukka Kohonen
  • 4.2k
  • 2
  • 21
  • 49

Having only the vertex orbits (instead of the full automorphism group) is not enough to compute the edge orbits. Consider, for example, a graph of $n=6$ vertices where all vertices are in a single orbit (in other words, the graph is vertex-transitivevertex-transitive). From this information, you cannot differentiate whether your graph is

Having only the vertex orbits (instead of the full automorphism group) is not enough to compute the edge orbits. Consider, for example, a graph of $n=6$ vertices where all vertices are in a single orbit (in other words, the graph is vertex-transitive). From this information, you cannot differentiate whether your graph is

  • $K_6$, which is also edge-transitive (all edges are in one orbit)
  • the triangular prism, which is not edge-transitive
  • or something else.

Having only the vertex orbits (instead of the full automorphism group) is not enough to compute the edge orbits. Consider, for example, a graph of $n=6$ vertices where all vertices are in a single orbit (in other words, the graph is vertex-transitive). From this information, you cannot differentiate whether your graph is

Source Link
Jukka Kohonen
Jukka Kohonen
  • 4.2k
  • 2
  • 21
  • 49

Having only the vertex orbits (instead of the full automorphism group) is not enough to compute the edge orbits. Consider, for example, a graph of $n=6$ vertices where all vertices are in a single orbit (in other words, the graph is vertex-transitive). From this information, you cannot differentiate whether your graph is

  • $K_6$, which is also edge-transitive (all edges are in one orbit)
  • the triangular prism, which is not edge-transitive
  • or something else.