0
$\begingroup$

Let $X = (V,E)$ be a graph whose edges are colored $( |V| = n)$ and assume that vertices are numbered from 1 to $n$. Now consider this group action: $$\pi : Aut(X) \times [n] \mapsto [n]$$

I know that $Aut(X)$ preserve the color of the edges i.e. it will map a red edge to red edge only.

I am interested in how orbits going to look in this situation. Are all red edges going to be in a single orbit and all blue edges going to be in a different orbit etc?

I tried on smaller graph, see the diagram below:

enter image description here

In the digram above, Is option 1 correct ?

In general, how the orbits are going to look like ?

EDIT : $Aut(X)$ also preserve the edge colours.

$\endgroup$
3
  • $\begingroup$ I don't know exactly what you mean by $\text{Aut}(X)$. Usually, the automorphism group of a graph does not care about the edge coloring. But if you want to look at the automorphisms that also fix edge coloring, then certainly $(1\;\;\;3)$ is not one. For whichever definition you are using, you should get a group. In fact, the set in item 2 is not a group. $\endgroup$ Aug 27, 2017 at 16:34
  • $\begingroup$ @Batominovski Why doesn't $(1\, 3)$ fix edge coloring? $\endgroup$ Aug 27, 2017 at 16:36
  • $\begingroup$ Sorry, I meant $(1\;\;\;2)$. $\endgroup$ Aug 27, 2017 at 17:41

2 Answers 2

0
$\begingroup$

enter image description here

For the non-edge-colored version, the automorphism group is going to be everything, i.e., the symmetric group $$\mathrm{Aut}(X)=\{\mathrm{id},(12),(13),(23),(123),(132)\}.$$ And we can compute there is a single edge orbit $$\{12,13,23\}.$$

Switching to the edge-colored version, we redefine what it means to be an automorphism. Here, automorphisms are not only permutations that maps edges to edges and non-edges to non-edges, but they also preserve edge colors.

enter image description here

By inspection $(13)$ is the only non-trivial permutation of the vertices that maps red edges to red edges and blue edges to blue edges. So we have $$\mathrm{Aut}(X_{\text{edge-col}})=\{\mathrm{id},(13)\}.$$

We can compute that there are two orbits under this group action $$\{13\}$$ since the edge $13$ maps to itself after permuting the vertices according to $\mathrm{id}$ and $(13)$ and $$\{12,23\}$$ since edge $12$ maps to itself after permuting the vertices according to $\mathrm{id}$ and maps to $23$ after permuting the vertices according to $(13)$.


Specific comments:

  • $(12)$ cannot be an automorphism of the edge-colored graph, as the blue edge $13$ maps to the red edge $(23)$.

  • Item 2. in the question is not a group, so it can't be the automorphism group of anything.

$\endgroup$
2
  • $\begingroup$ Thanks for the answer, how in general orbit going to look like ? $\endgroup$
    – user275490
    Aug 27, 2017 at 16:43
  • $\begingroup$ It's the same process with or without colors: compute the automorphism group, and for any edge $ij$ and each automorphism $\alpha$ see where $\alpha$ maps $ij$. Together, that's the orbit of $ij$. $\endgroup$ Aug 27, 2017 at 16:44
0
$\begingroup$

In general, edges of the same colour will not necessarily be in the same orbit. For instance, consider a square with three edges coloured red and one blue. In this case Aut(X) has three orbits of edges.

In fact, even if you use only one colour, edges don't have to be in the same orbit. It's possible for a graph with $m$ edges ($m \ge 6$) to have no automorphisms at all except the trivial one.

$\endgroup$
2
  • $\begingroup$ I think for square with three edges coloured red and one blue, there are going to be two orbits, because Automorphism(X) preserve the edge color . $\endgroup$
    – user275490
    Aug 27, 2017 at 18:07
  • $\begingroup$ No, because a graph automorphism also needs to preserve adjacency. There's one red edge that is not adjacent to the blue edge - think about where this edge can go under an automorphism. $\endgroup$
    – Colin
    Aug 28, 2017 at 0:40

You must log in to answer this question.