Distance-balanced graphs: Symmetry conditions

Kutnar, Klavdija; Malnič, Aleksander; Marušič, Dragan; Miklavič, Štefko

SLO

First page / Show document

Show document

A- | A+ | Print

Title:	Distance-balanced graphs: Symmetry conditions
Authors:	ID Kutnar, Klavdija (Author) ID Malnič, Aleksander (Author) ID Marušič, Dragan (Author) ID Miklavič, Štefko (Author)
Files:	http://dx.doi.org/10.1016/j.disc.2006.03.066
Language:	English
Work type:	Not categorized
Typology:	1.01 - Original Scientific Article
Organization:	IAM - Andrej Marušič Institute
Abstract:	A graph $X$ is said to be 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 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$ . Exploring the connection between symmetry properties of graphs and the metric property of being (strongly) distance-balanced is the main theme of this article. That a vertex-transitive graph is necessarily strongly distance-balanced and thus also distance-balanced is an easy observation. With only a slight relaxation of the transitivity condition, the situation changes drastically: there are infinite families of semisymmetric graphs (that is, graphs which are edge-transitive, but not vertex-transitive) which are distance-balanced, but there are also infinite families of semisymmetric graphs which are not distance-balanced. Results on the distance-balanced property in product graphs prove helpful in obtaining these constructions. Finally, a complete classification of strongly distance-balanced graphs is given for the following infinite families of generalized Petersen graphs: GP $(n,2)$ , GP $(5k+1,k)$ , GP $(3k 3,k)$ , and GP $(2k+2,k)$ .
Keywords:	graph theory, graph, distance-balanced graphs, vertex-transitive, semysimmetric, generalized Petersen graph
Year of publishing:	2006
Number of pages:	str. 1881-1894
Numbering:	Vol. 306, iss. 16
PID:	20.500.12556/RUP-835
ISSN:	0012-365X
UDC:	519.17
COBISS.SI-ID:	1714391
Publication date in RUP:	15.10.2013
Views:	6930
Downloads:	93
Metadata:
:	KUTNAR, Klavdija, MALNIČ, Aleksander, MARUŠIČ, Dragan and MIKLAVIČ, Štefko, 2006, Distance-balanced graphs: Symmetry conditions. [online]. 2006. Vol. 306, no. 16, p. 1881–1894. [Accessed 19 March 2025]. Retrieved from: http://dx.doi.org/10.1016/j.disc.2006.03.066 Copy citation