How can we find the proof of the following statement: An undirected graph is edge transitive if and only if its line graph is vertex transitive.
$\begingroup$
$\endgroup$
4
-
$\begingroup$ You use the definitions of -transitivity and line graph. You should be able to show something stronger as easily, that every automorphism which moves an edge in G corresponds to an automorphism of L(G) that moves a vertex, and vice versa. Try finding and using such a correspondence. $\endgroup$– The Masked AvengerJul 19, 2014 at 16:46
-
6$\begingroup$ $G=K_3+K_{1,3}$ is a counterexample. The line-graph of $G$ is vertex transitive but $G$ is not edge transitive. $\endgroup$– Jan KynclJul 19, 2014 at 21:26
-
$\begingroup$ If we use regular graph for this statement, then what is the answer? $\endgroup$– Mojtaba JazaeriJul 19, 2014 at 21:47
-
$\begingroup$ Do you know of any connected counterexamples @Jan? $\endgroup$– The Masked AvengerJul 20, 2014 at 2:06
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
G. Sabidussi, Math. Zeitschr. 76, 385-401 (1961) proved that the automorphism group of a (simple) connected graph is isomorphic to the automorphism group of its linegraph, with the obvious isomorphism, unless the graph is one of four exceptions: the complete graphs $K_2$ and $K_4$, a triangle with an extra edge attached, and two triangles sharing an edge. Sabidussi also gave a new proof of a theorem earlier proved by Whitney, namely that the only two non-isomorphic connected graphs with isomorphic linegraphs are the triangle and the 3-star $K_{1,3}$.
We also need to think about isolated vertices, since they vanish without trace in the line graph. But they aren't really a problem since they don't affect edge-transitivity.
Putting all this together, we find that the only exceptions to the claim "a graph is edge transitive if and only if its line graph is vertex transitive" are disconnected graphs whose components are all $K_1$, $K_3$ or $K_{1,3}$, with at least one $K_3$ and at least one $K_{1,3}$.
answered Jul 20, 2014 at 2:40