Strongly distance-balanced graphs and graph products
type: Item
instance of: scholarly article
title: Strongly distance-balanced graphs and graph products
zbMATH Open document ID: 1185.05052
author: Kannan Balakrishnan
author: Manoj Changat
author: Iztok Peterin
author: Simon Špacapan
author: Primož Šparl
author: Ajitha R. Subhamathi
published in: European Journal of Combinatorics
publication date: 2009-06-17T00:00:00Z
review text: A graph \(G\) is distance-balanced if for every edge \(uv\in E(G)\), \[ \left|\left\{x\mid d(u,x) < d(v,x)\right\}\right| = \left|\left\{x\mid d(v,x) < d(u,x)\right\}\right|, \] where \(d(u,v)\) is the length of a shortest path between \(u\) and \(v\) in \(G\). \(G\) is strongly distance-balanced if for every edge \(uv\in E(G)\) and every \(i\geq 0\) the number of vertices \(x\in V(G)\) with \(d(x,u)=d(x,v)-1=i\) equals the number of vertices \(y\in V(G)\) with \(d(y,v)= d(y,u)-1=i\). The vertex set of the Cartesian product/the direct product/the strong product of two graphs \(G\) and \(H\) is \(V(G)\times V(H)\). In the Cartesian product \(G\square H\) two vertices are adjacent if they are adjacent in one coordinate and equal in the other. In the direct product \(G\times H\) two vertices are adjacent if they are adjacent in both coordinates. The edge set of the strong product \(G\boxtimes H\) is the union of \(E(G\square H)\) and \(E(G\times H)\). The results of the paper are: {\parindent=6mm \begin{itemize}\item[(1)]\(G\boxtimes H\) is strongly distance-balanced if and only if \(G\) and \(H\) are strongly distance-balanced. \item[(2)]Let \(G\) and \(H\) be connected bipartite graphs. Then the connected components of \(G\times H\) are strongly distance-balanced if and only if \(G\) and \(H\) are strongly distance-balanced. \item[(3)]A connected graph \(G\) is distance-balanced if and only if \(M(G)=V(G)\), where \(M(G)\) is the set of all vertices \(x\) of \(G\) for which \(\sum_{v\in V(G)} d(x,v)\) is minimal among all vertices of \(G\). \end{itemize}} It follows from (3) that recognizing if a graph \(G\) is distance-balanced can be done in \(O\left(|V(G)|\cdot |E(G)|\right)\) time.
reviewed by: Van Bang Le
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C76
zbMATH DE Number: 5565550
zbMATH Keywords: distance-balanced graph
zbMATH Keywords: strongly distance-balanced graph
zbMATH Keywords: graph product
MaRDI profile type: Publication
full work available at URL: j.ejc.2008.09.018
OpenAlex ID: W2056944495
cites work: Graphs with connected medians
cites work: Q5463557
cites work: Bipartite graphs with balanced \((a,b)\)-partitions
cites work: Q4523707
cites work: Distance-balanced graphs
cites work: Q4028285
cites work: Q4677949
cites work: Distance-balanced graphs: symmetry conditions
cites work: The strongly distance-balanced property of the generalized Petersen graphs
cites work: Medians of arbitrary graphs
DOI: 10.1016/J.EJC.2008.09.018
description: scientific article; zbMATH DE number 5565550