Connection Between Automorphism Groups of a Graph and its Line Graph

First, the specific case I'm trying to handle is this:

I have the graph $\Gamma = K_{4,4}$.

I understand that its automorphism group is the wreath product of $S_4 \wr S_2$ and thus it is a group of order 24*24*2=1152.

My goal is to find the order of the AUTOMORPHISM GROUP of the Line Graph: $L(\Gamma)$. That is - $|Aut(L(G))|$

I used GAP and I already know that the answer is 4608, which just happens to be 4*1152.

I guess this isn't a coincidence. Is there some sort of an argument which can give me this result theoretically?

Also, I would use this thread to ask about information of this problem in general (Connection Between Automorphism Groups of a Graph and its Line Graph).

I suppose that there is no general case theorem.

I was told by one of the professors in my department that "for a lot of cases, there is a general rule of thumb that works" although no more details were supplied. If anyone has an idea what he was referring to, I'd be happy to know.

Lost_DM

• Are you sure about the order of Aut(L(K(4,4)))? Size(AutomorphismGroup(EdgeGraph(EdgeOrbitsGraph(WreathProduct(SymmetricGroup(4),SymmetricGroup(2)),[1,5])))); gives 1152 for me. – Jack Schmidt Jul 27 '11 at 15:34

The automorphism group of a graph and the automorphism group of its line graph are very closely related. The latter is also called its edge automorphism group and was studied by Whitney (1932).

There is a homomorphism from Aut(Γ) to Aut(L(Γ)) for any simple graph Γ.

The kernel is the group of permutations of the vertices contained in connected components of size at most 2. In particular, avoid (more than one) isolated vertices and connected components of type K2 and you always have an injection.

The image of Aut(Γ) is almost always all of Aut(L(Γ)). There are exactly 3 connected exceptions. A graph Γ is an exception if and only if it has one of these connected exceptions as a connected component, or if it has a certain pair of components (K1,3 and K3). You can calculate the index fairly easily from the list of exceptional components in your Γ; the index is $2^k \binom{m+n}{n}$, where Γ has k exceptional connected components and m connected components that are K1,3, and n connected components that are K3.

In particular, for Γ = K4,4, the homomorphism from Aut(Γ) to Aut(L(Γ)) is an isomorphism.

This is known as Whitney's theorem, from Whitney (1932). An easier to read version is in the introductory chapter (pp. 11-13) of Lauri–Scapellato (2003), but only the kernel is proven. A weaker corollary is described in the wikipedia article, and the paper itself is concerned with strong connectivity. Hemminger (1972) has a nice description of the exceptions and why they occur (as well as references to two other simpler proofs and their textbook presentations). Jung (1966) is quite short and fairly easy to read (in German).

• Whitney, Hassler; Congruent Graphs and the Connectivity of Graphs. Amer. J. Math. 54 (1932), no. 1, 150–168. MR1506881 Zbl3.32804 DOI:10.2307/2371086

• Jung, H. A. Zu einem Isomorphiesatz von H. Whitney für Graphen. Math. Ann. 164 (1966) 270–271. MR197353 DOI:10.1007/BF01360250

• Hemminger, R. L. On Whitney's line graph theorem. Amer. Math. Monthly 79 (1972), 374–378. MR299514 DOI:10.2307/2978089

• Lauri, Josef; Scapellato, Raffaele. Topics in graph automorphisms and reconstruction. London Mathematical Society Student Texts, 54. Cambridge University Press, Cambridge, 2003. xii+159 pp. ISBN: 0-521-82151-7; 0-521-52903-4 MR1971819

I'm not sure if this is what you are asking, but there is always a map from $\mbox{Aut}(G)$ to $\mbox{Aut}(L(G))$ that is an injection in your case, explaining your divisibility relation. If $\phi$ is an automorphism of $G$, then $\phi$ also acts on $L(G)$: $\phi$ already knows what to do to vertices of $L(G)$ (which are edges of $G$), and $\phi$ also preserves the edge incidence relation, so extends to a map on edges of $L(G)$. This is not always an injection: consider the case of the graph with a single edge connecting distinct vertices. But in your case the map is an injection, which explains your divisibility relation.

• Very good. This is close to what I'm looking for. Now I only wish to explain why $Aut(G)$ is a subgroup of index 4 in $Aut(L(G))$ – Lost_DM Jul 27 '11 at 14:34

The order of a graph usually refers to the number of vertices. The line graph of $K_{4,4}$ has 16 vertices since this is the number of edges in $K_{4,4}$. The number of edges in $L(K_{4,4})$ is 48 since it's a 6-regular graph. I'm not sure where 4608 comes from. Are you referring to the automorphism group of the line graph?

Your graph $\Gamma$ is very symmetric and so there can be various numerical coincidences between its symmetry group, its number of edges, number of pairs of incident edges etc.

In general you should not expect a relationship between the automorphism group and the line graph (again, are you really comparing $\mbox{Aut}(G)$ and $L(G)$, or $\mbox{Aut}(G)$ and $\mbox{Aut}(L(G))$?). Most graphs have no non-trivial automorphisms at all, while they do of course have non-trivial line graphs. The automorphism group "measures" global symmetry, while the line graph just represents the incidences between edges and is "unaware" of the global structure.

• I'm compering $Aut(G)$ and $Aut(L(G))$. 4608 is the order of $Aut(L(G))$ According to GAP. You are correct, I wasn't clear on that. Edited original msg. Thanks! – Lost_DM Jul 27 '11 at 14:34

If G is a graph with minimum valency (degree) 4, then Aut(G) is group-theoritical isomorphic to Aut(L(G)). See Godsil & Royle, Algebraic graph theory exercise 1.15. The proof is not too hard.