Distance-balanced graphs: symmetry conditions
| dc.creator | Kutnar, K. | |
| dc.creator | Malnic, A. | |
| dc.creator | Marusic, D. | |
| dc.creator | Miklavic, S. | |
| dc.date | 2005-10-18 | |
| dc.date.accessioned | 2026-07-07T06:47:37Z | |
| dc.date.available | 2026-07-07T06:47:37Z | |
| dc.description | A graph $X$ is said to be {\it distance--balanced} if for any edge $uv$ of $X$, the number of vertices closer to $u$ than to $v$ is equal to the number of vertices closer to $v$ than to $u$. A graph $X$ is said to be {\it strongly distance--balanced} if for any edge $uv$ of $X$ and any integer $k$, the number of vertices at distance $k$ from $u$ and at distance $k+1$ from $v$ is equal to the number of vertices at distance $k+1$ from $u$ and at distance $k$ from $v$. Obviously, being distance--balanced is metrically a weaker condition than being strongly distance--balanced. In this paper, a connection between symmetry properties of graphs and the metric property of being (strongly) distance--balanced is explored. In particular, it is proved that every vertex--transitive graph is strongly distance--balanced. A graph is said to be {\em semisymmetric} if its automorphism group acts transitively on its edge set, but does not act transitively on its vertex set. An infinite family of semisymmetric graphs, which are not distance--balanced, is constructed. Finally, we give a complete classification of strongly distance--balanced graphs for the following infinite families of generalized Petersen graphs: $\GP(n,2)$, $\GP(5k+1,k)$, $\GP(3k\pm 3,k)$, and $\GP(2k+2,k)$. | |
| dc.description | 12 pages, 4 figures | |
| dc.identifier | https://arxiv.org/abs/math/0510381 | |
| dc.identifier | http://arxiv.org/abs/math/0510381 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/103711 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C07; 05C12 | |
| dc.title | Distance-balanced graphs: symmetry conditions | |
| dc.type | text |