Symmetry properties of subdivision graphs

DOI10.1016/J.DISC.2011.03.031zbMATH Open1238.05130arXiv1008.2261OpenAlexW2085039110WikidataQ56987620 ScholiaQ56987620MaRDI QIDQ658022FDOQ658022

Ashraf Daneshkhah, Cheryl E. Praeger, Alice Devillers

Publication date: 11 January 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The nonexistence of 8-transitive graphs
• On the Symmetry of Cubic Graphs
• On Moore Graphs with Diameters 2 and 3
• Analysing finite locally 𝑠-arc transitive graphs
• Title not available (Why is that?)
• Locally s-distance transitive graphs
• Notes on infinite permutation groups
• Finite primitive distance-transitive graphs
• On the Sims Conjecture and Distance Transitive Graphs
• Intersection matrices for finite permutation groups
• Distance Transitive Graphs and Finite Simple Groups
• On 2-transitive graphs of girth 5

Cited In (4)

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

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)