Strongly distance-balanced graphs and graph products (Q1024301): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.ejc.2008.09.018 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2056944495 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Graphs with Connected Medians / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5463557 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2761049 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4523707 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Distance-balanced graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4028285 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4677949 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Distance-balanced graphs: symmetry conditions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The strongly distance-balanced property of the generalized Petersen graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Medians of arbitrary graphs / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 16:44, 1 July 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