Symmetry properties of subdivision graphs

DOI10.1016/J.DISC.2011.03.031MaRDI QIDQ658022zbMATH OpenOpenAlexWikidataFDO

Authors Ashraf Daneshkhah, Alice Devillers, Cheryl E. Praeger

Publication date 11 January 2012

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1008.2261

zbMATH Keywords

line graphsubdivision graphlocally \(s\)-arc transitive graphlocally distance transitive graph

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Abstract: The subdivision graph $S(Sigma)$ of a graph $Sigma$ is obtained from $Sigma$ by `adding a vertex' in the middle of every edge of $Si$. Various symmetry properties of $S(Sigma)$ are studied. We prove that, for a connected graph $Sigma$, $S(Sigma)$ is locally $s$-arc transitive if and only if $Sigma$ is $lceilfracs+12ceil$-arc transitive. The diameter of $S(Sigma)$ is $2d+delta$, where $Sigma$ has diameter $d$ and $0leqslantdeltaleqslant2$, and local $s$-distance transitivity of $S(Sigma)$ is defined for $1leqslantsleqslant2d+delta$. In the general case where $sleqslant2d-1$ we prove that $S(Sigma)$ is locally $s$-distance transitive if and only if $Sigma$ is $lceilfracs+12ceil$-arc transitive. For the remaining values of $s$, namely $2dleqslantsleqslant2d+delta$, we classify the graphs $Sigma$ for which $S(Sigma)$ is locally $s$-distance transitive in the cases, $sleqslant5$ and $sgeqslant15+delta$. The cases $max2d,6leqslantsleqslantmin2d+delta,14+delta$ remain open.

Recommendations

• Publication:4888415
• Symmetry in Graphs
• Graph decompositions and symmetry
• Symmetry properties of generalized graph truncations
• Generalized symmetry of graphs
• Symmetry breaking in graphs
• scientific article; zbMATH DE number 3882462
• scientific article; zbMATH DE number 2016066
• scientific article; zbMATH DE number 704530
• On several symmetry conditions for graphs

Cites work

• scientific article; zbMATH DE number 3906699 (Why is no real title available?)
• scientific article; zbMATH DE number 3445271 (Why is no real title available?)
• scientific article; zbMATH DE number 894528 (Why is no real title available?)
• scientific article; zbMATH DE number 3046496 (Why is no real title available?)
• Analysing finite locally 𝑠-arc transitive graphs
• Distance Transitive Graphs and Finite Simple Groups
• Finite primitive distance-transitive graphs
• Intersection matrices for finite permutation groups
• Locally \(s\)-distance transitive graphs
• Notes on infinite permutation groups
• On 2-transitive graphs of girth 5
• On Moore Graphs with Diameters 2 and 3
• On the Sims Conjecture and Distance Transitive Graphs
• On the Symmetry of Cubic Graphs
• The nonexistence of 8-transitive graphs

Cited in

(5)

• Cyclic deficiency of graphs
• Some algebraic properties of the subdivision graph of a graph
• A classification of graphs whose subdivision graph is locally distance transitive
• Locally \(s\)-distance transitive graphs
• The \((a,b)\)-Zagreb index of line graphs of subdivision graphs of some molecular structures

This page was built for publication: Symmetry properties of subdivision graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q658022)