Line graphs and geodesic transitivity

Alice Devillers, Wei Jin, Cai Heng Li, Cheryl E. Praeger


For a graph Γ, a positive integer s and a subgroup G ≤ Aut(Γ), we prove that G is transitive on the set of s-arcs of Γ if and only if Γ has girth at least 2(s − 1) and G is transitive on the set of (s − 1)-geodesics of its line graph. As applications, we first classify 2-geodesic transitive graphs of valency 4 and girth 3, and determine which of them are geodesic transitive. Secondly we prove that the only non-complete locally cyclic 2-geodesic transitive graphs are the octahedron and the icosahedron.


Line graphs, s-geodesic transitive graphs, s-arc transitive graphs.

Full Text:



ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications