Mathematics – Combinatorics
Scientific paper
2005-10-18
Mathematics
Combinatorics
12 pages, 4 figures
Scientific paper
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)$.
Kutnar Klavdija
Malnic Aleksander
Marusic Dragan
Miklavic Stefko
No associations
LandOfFree
Distance-balanced graphs: symmetry conditions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Distance-balanced graphs: symmetry conditions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distance-balanced graphs: symmetry conditions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-194385