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:
“The rage for road building is beneficent for America, where vast distance is so main a consideration in our domestic politics and trade, inasmuch as the great political promise of the invention is to hold the Union staunch, whose days already seem numbered by the mere inconvenience of transporting representatives, judges and officers across such tedious distances of land and water.”
—Ralph Waldo Emerson (1803–1882)
“After climbing a great hill, one only finds that there are many more hills to climb. I have taken a moment here to rest, to steal a view of the glorious vista that surrounds me, to look back on the distance I have come. But I can rest only for a moment, for with freedom comes responsibilities, and I dare not linger, for my long walk is not yet ended.”
—Nelson Mandela (b. 1918)
“We have been told over and over about the importance of bonding to our children. Rarely do we hear about the skill of letting go, or, as one parent said, “that we raise our children to leave us.” Early childhood, as our kids gain skills and eagerly want some distance from us, is a time to build a kind of adult-child balance which permits both of us room.”
—Joan Sheingold Ditzion (20th century)