Title of article :
Symmetry properties of subdivision graphs
Author/Authors :
Daneshkhah، نويسنده , , Ashraf and Devillers، نويسنده , , Alice and Praeger، نويسنده , , Cheryl E.، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2012
Pages :
8
From page :
86
To page :
93
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 + 1 2 ⌉ -arc transitive. The diameter of S ( Σ ) is 2 d + δ , where Σ has diameter d and 0 ⩽ δ ⩽ 2 , and local s -distance transitivity of S ( Σ ) is defined for 1 ⩽ s ⩽ 2 d + δ . In the general case where s ⩽ 2 d − 1 we prove that S ( Σ ) is locally s -distance transitive if and only if Σ is ⌈ s + 1 2 ⌉ -arc transitive. For the remaining values of s , namely 2 d ⩽ s ⩽ 2 d + δ , we classify the graphs Σ for which S ( Σ ) is locally s -distance transitive in the cases, s ⩽ 5 and s ⩾ 15 + δ . The cases max { 2 d , 6 } ⩽ s ⩽ min { 2 d + δ , 14 + δ } remain open.
Keywords :
Locally s -arc transitive graph , Line graph , Locally distance transitive graph , Subdivision graph
Journal title :
Discrete Mathematics
Serial Year :
2012
Journal title :
Discrete Mathematics
Record number :
1599781
Link To Document :
بازگشت