I am trying to apply the main theorem of this paper to a certain kind of graph and keep getting confused. The theorem uses $rank(Aut\Gamma)$ which is defined as "the number of $Aut \Gamma$ orbits on the set $V(\Gamma) \times V(\Gamma)$". ($\Gamma$ is a graph).

Now, my graph $\Gamma$ is built in this way: take a clique of $c$ vertices, labelled $\{1,2,\ldots,c\}$ and add $s=\binom{c-1}{2}$ additional vertices, each of which is connected to a different pair of two vertices from $\{2,\ldots,c\}$.

Question: What is $rank(Aut\Gamma)$?

My answer is 9 because the automorphism group is (apparently) $S_{c-1} \times S_{s}$ and there are 3 orbits for it. However, when I plug 9 into the theorem I get a contradiction with the rest of it (which involves objects I have a better grasp of so I am pretty sure I got the rest right).

Therefore, I suspect that my answer to the above question is wrong and I am in dire need of some enlightenment.

EDIT: Let's assume $c \geq 4$ to rule out sporadic cases.

  • $\begingroup$ You count three orbits of the group on $V(\Gamma)$. And on $V(\Gamma)\times V(\Gamma)$? $\endgroup$ Dec 24, 2012 at 15:38
  • $\begingroup$ Unless I misunderstood the description of the graphs, your automorphism group seems to be wrong, for example when $c=3$, the automorphism group of $\Gamma$ is $S_2\times S_2$, not $S_2\times S_1$ as your formula posits and for $c\geq 4$, the automorphism group seems to be just $S_{c-1}$. $\endgroup$
    – ARupinski
    Dec 24, 2012 at 15:49
  • $\begingroup$ @Mariano: Like I said, I get 9, but it seems to be wrong... $\endgroup$ Dec 24, 2012 at 15:56
  • $\begingroup$ I don't understand why you say that «you count 3 orbits but you plug in $9$». $\endgroup$ Dec 24, 2012 at 15:59
  • $\begingroup$ @ARupinski: Let's assume $c \geq 4$ (I'll update the question too). $\endgroup$ Dec 24, 2012 at 16:02

2 Answers 2


The automorphism group of this graph is $S_{c-1}$. Note that the vertex 1 in your clique cannot be moved anywhere (look at the degrees). On the other hand, a permutation of the remaining vertices in {2,...,c} induces a permutation on these $s$ vertices $P$. The 14 orbitals (aka orbits on $V\times V$) are as follows:

  1. {(1,1)}
  2. {(x,x) | x in {2..c}}
  3. {(p,p) | p in P}
  4. {(x,y) | x,y in {2..c}, x not equal to y}
  5. {(p,q) | p,q in P, the corresponding pairs of elements of {2..c} do not intersect}
  6. {(p,q) | p,q in P, the corresponding pairs of elements of {2..c} intersect in one element}
  7. {(1,x) | x in {2..c}}
  8. {(x,1) | x in {2..c}}
  9. {(1,p) | p in P}
  10. {(p,1) | p in P}
  11. {(x,p) | x in {2..c}, p in P, x in p}
  12. {(p,x) | x in {2..c}, p in P, x in p}
  13. {(x,p) | x in {2..c}, p in P, x not in p}
  14. {(p,x) | x in {2..c}, p in P, x not in p}

First, let me point out that I think ARupinski is right and $\rm{Aut}(\Gamma)$ is simply $S_{c-1}$. (This could be relevant.)

Next, note that there are at least 11 orbits on $V(\Gamma)\times V(\Gamma)$.

There is an obvious partition into 9 parts (coming from the 3 orbits on $V(\Gamma)$) each belonging to a different orbit, but 2 of these split into two orbits, a diagonal part and a non-diagonal part.

For example $(2,2)$ is in a different orbit than $(2,3)$.

In fact, there are even more orbits than this. For example, the part corresponding to $s\times s$ splits even further : ({1,2},{2,3}) is not in the same orbit as ({1,2},{3,4}). The first is an ordered pair of vertices having a neighbour in common, while the second is a pair of vertices with no neighbour in common.

EDIT: As Dima Pasechnik explained, two of the other parts also split further in two, for a total of 14 orbits.


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.