Strongly distance-balanced graphs and graph products (Q1024301): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 02:56, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Strongly distance-balanced graphs and graph products |
scientific article |
Statements
Strongly distance-balanced graphs and graph products (English)
0 references
17 June 2009
0 references
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.
0 references
distance-balanced graph
0 references
strongly distance-balanced graph
0 references
graph product
0 references