Line graphs and geodesic transitivity
Keywords:Line graphs, s-geodesic transitive graphs, s-arc transitive graphs.
AbstractFor 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.
Special Issue Bled'11
Articles in this journal are published under Creative Commons Attribution 4.0 International License