The distance dG(u, v) between two (not necessary distinct) vertices u and v in a graph G is the length of a shortest path between them. The subscript G is usually dropped when there is no danger of confusion. When u and v are identical, their distance is 0. When u and v are unreachable from each other, their distance is defined to be infinity ∞.
The eccentricity εG(v) of a vertex v in a graph G is the maximum distance from v to any other vertex. The diameter diam(G) of a graph G is the maximum eccentricity over all vertices in a graph; and the radius rad(G), the minimum. When there are two components in G, diam(G) and rad(G) defined to be infinity ∞. Trivially, diam(G) ≤ 2 rad(G). Vertices with maximum eccentricity are called peripheral vertices. Vertices of minimum eccentricity form the center. A tree has at most two center vertices.
The Wiener index of a vertex v in a graph G, denoted by WG(v) is the sum of distances between v and all others. The Wiener index of a graph G, denoted by W(G), is the sum of distances over all pairs of vertices. An undirected graph's Wiener polynomial is defined to be Σ qd(u,v) over all unordered pairs of vertices u and v. Wiener index and Wiener polynomial are of particular interest to mathematical chemists.
The k-th power Gk of a graph G is a supergraph formed by adding an edge between all pairs of vertices of G with distance at most k. A second power of a graph is also called a square.
A k-spanner is a spanning subgraph, S, in which every two vertices are at most k times as far apart on S than on G. The number k is the dilation. k-spanner is used for studying geometric network optimization.
Read more about this topic: Glossary Of Graph Theory
Famous quotes containing the word distance:
“A petty reason perhaps why novelists more and more try to keep a distance from journalists is that novelists are trying to write the truth and journalists are trying to write fiction.”
—Graham Greene (1904–1991)
“It is the simplest relation of phenomena, and describes the commonest sensations with more truth than science does, and the latter at a distance slowly mimics its style and methods.”
—Henry David Thoreau (1817–1862)
“Let me approach at least, and touch thy hand.
[Samson:] Not for thy life, lest fierce remembrance wake
My sudden rage to tear thee joint by joint.
At distance I forgive thee, go with that;
Bewail thy falsehood, and the pious works
It hath brought forth to make thee memorable
Among illustrious women, faithful wives:
Cherish thy hast’n’d widowhood with the gold
Of Matrimonial treason: so farewel.”
—John Milton (1608–1674)