Article ID Journal Published Year Pages File Type
6423526 Discrete Mathematics 2012 8 Pages PDF
Abstract

The subdivision graph S(Σ) of a graph Σ is obtained from Σ by 'adding a vertex' in the middle of every edge of Σ. Various symmetry properties of S(Σ) are studied. We prove that, for a connected graph Σ, S(Σ) is locally s-arc transitive if and only if Σ is ⌈s+12⌉-arc transitive. The diameter of S(Σ) is 2d+δ, where Σ has diameter d and 0⩽δ⩽2, and local s-distance transitivity of S(Σ) is defined for 1⩽s⩽2d+δ. In the general case where s⩽2d−1 we prove that S(Σ) is locally s-distance transitive if and only if Σ is ⌈s+12⌉-arc transitive. For the remaining values of s, namely 2d⩽s⩽2d+δ, we classify the graphs Σ for which S(Σ) is locally s-distance transitive in the cases, s⩽5 and s⩾15+δ. The cases max{2d,6}⩽s⩽min{2d+δ,14+δ} remain open.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,