From Distances to Eccentricity
A distance table records the lengths of shortest paths between vertices. Once the table is available, two related questions can be answered one row at a time: how far is a vertex from its most distant vertex, and which vertices attain that distance? The maximum in a row gives the first answer; the column labels at that maximum give the second. There may be more than one such column, so it is important to report all farthest vertices rather than select one arbitrarily.
Throughout, graphs are finite and simple. Unless stated otherwise, \(G=(V,E)\) is connected and has at least one vertex. The distance \(d(u,v)\) is the length of a shortest \(u\)-\(v\) path. In a connected graph each such distance is a finite nonnegative integer, and \(d(v,v)=0\).
The maximum exists because \(V(G)\) is finite and nonempty, so \(F_G(v)\) is always nonempty. If \(G\) has just one vertex \(v\), then the only distance in its row is \(d(v,v)=0\). Thus \(\operatorname{ecc}_G(v)=0\) and \(F_G(v)=\{v\}\). In a graph with more vertices, a vertex is not usually its own farthest vertex, because its distance to itself is zero while its distance to at least one other vertex is positive.
For a connected graph, a distance table is a square table whose rows and columns are labelled by the vertices. Its entry in row \(v\), column \(u\) is \(d(v,u)\). The eccentricity is the largest entry in row \(v\); the farthest-vertex set consists of the column labels at which that largest entry appears. In an undirected graph the table is symmetric, since reversing a path from \(u\) to \(v\) gives a path of the same length from \(v\) to \(u\). The diagonal entries are zero.
Reading a Distance Table
To use a table reliably, first identify the row and its largest entry. Then list every column label with that value. Do not confuse the maximum distance with the number of vertices at that distance: the maximum is the eccentricity, while all the attaining vertices form a set. A tie changes the size of the farthest-vertex set but does not change the eccentricity.
Worked Example: The Distance Table of a Path
Let \(G\) have vertex set \(V=\{1,2,3,4,5\}\) and edge set \(E=\{12,23,34,45\}\). This is a path with five vertices. There is a unique path between each pair, so the distance between two vertices is the number of edges between their labels along the path. The full distance table is:
| \(d(u,v)\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) |
|---|---|---|---|---|---|
| \(1\) | 0 | 1 | 2 | 3 | 4 |
| \(2\) | 1 | 0 | 1 | 2 | 3 |
| \(3\) | 2 | 1 | 0 | 1 | 2 |
| \(4\) | 3 | 2 | 1 | 0 | 1 |
| \(5\) | 4 | 3 | 2 | 1 | 0 |
For vertex \(1\), the row is \(0,1,2,3,4\). Its maximum is \(4\), at column \(5\), so \(\operatorname{ecc}_G(1)=4\) and \(F_G(1)=\{5\}\). For vertex \(2\), the row is \(1,0,1,2,3\); its maximum is \(3\), at column \(5\), so \(\operatorname{ecc}_G(2)=3\) and \(F_G(2)=\{5\}\). For vertex \(3\), the row is \(2,1,0,1,2\); its maximum is \(2\), attained at columns \(1\) and \(5\), so \(\operatorname{ecc}_G(3)=2\) and \(F_G(3)=\{1,5\}\). For vertex \(4\), the row is \(3,2,1,0,1\); its maximum is \(3\), at column \(1\), so \(\operatorname{ecc}_G(4)=3\) and \(F_G(4)=\{1\}\). For vertex \(5\), the row is \(4,3,2,1,0\); its maximum is \(4\), at column \(1\), so \(\operatorname{ecc}_G(5)=4\) and \(F_G(5)=\{1\}\).
Check: The maximum occurs once in rows \(1,2,4,5\), and twice in row \(3\). In particular, the farthest-vertex sets from \(1,2,3,4,5\) are, respectively, \(\{5\},\{5\},\{1,5\},\{1\},\{1\}\). The table is symmetric: for example, the entry \(d(1,5)=4\) agrees with \(d(5,1)=4\). Along the path, the distance from \(1\) to \(5\) is \(4\) edges, matching the table.
When calculating a table from a graph rather than being given one, it helps to organize the calculation by distance layers. Starting from a chosen vertex \(v\), put \(v\) in layer \(0\), its neighbors in layer \(1\), and each not-yet-listed vertex adjacent to the current layer into the next layer. The first layer in which a vertex appears gives its shortest-path distance from \(v\): any route reaching it earlier would have put it into an earlier layer. Repeat from each row vertex, or use a previously established distance table.
Basic Properties
Proof. Every distance is a nonnegative integer, so the maximum of the distances from \(v\) is nonnegative. For the upper bound, take any vertex \(u\). Because the graph is connected, there is a shortest path from \(v\) to \(u\). A shortest path cannot repeat a vertex: if it did, the portion between two occurrences could be removed to produce a shorter path with the same endpoints. Thus the path uses distinct vertices. It can use at most all \(n\) vertices, and so has at most \(n-1\) edges. Therefore \(d(v,u)\leq n-1\) for every \(u\in V(G)\). Taking the maximum over \(u\) gives \(\operatorname{ecc}_G(v)\leq n-1\). When \(n=1\), the only distance is zero, so both bounds hold. \(\square\)
The path argument also explains why distances in a connected graph with \(n\) vertices cannot exceed \(n-1\), even if a graph has many edges. Extra edges may create shorter routes, but cannot require a shortest route to repeat vertices.
Proof. Let \(x\) be any vertex. Since \(uv\) is an edge, a route from \(u\) to \(x\) can begin with \(uv\) and then follow a shortest \(v\)-\(x\) path. Its length is \(1+d(v,x)\), so \(d(u,x)\leq 1+d(v,x)\). Since \(d(v,x)\leq \operatorname{ecc}_G(v)\), this gives \(d(u,x)\leq 1+\operatorname{ecc}_G(v)\) for every \(x\). Taking the maximum over \(x\) proves \(\operatorname{ecc}_G(u)\leq 1+\operatorname{ecc}_G(v)\). Interchanging \(u\) and \(v\) gives the other inequality. \(\square\)
This proposition concerns adjacent vertices only. It does not say that all vertices have the same eccentricity, nor that their eccentricities must differ by exactly one. They may be equal, as in the next example.
Worked Example: Every Vertex in a Four-Cycle
Let \(G\) have \(V=\{1,2,3,4\}\) and \(E=\{12,23,34,41\}\), a cycle on four vertices. From vertex \(1\), the distance layers are \(\{1\}\), \(\{2,4\}\), and \(\{3\}\). Thus the distances in row \(1\) are \(0,1,2,1\). Rotating this same layer calculation to each starting vertex gives:
| \(d(u,v)\) | \(1\) | \(2\) | \(3\) | \(4\) |
|---|---|---|---|---|
| \(1\) | 0 | 1 | 2 | 1 |
| \(2\) | 1 | 0 | 1 | 2 |
| \(3\) | 2 | 1 | 0 | 1 |
| \(4\) | 1 | 2 | 1 | 0 |
Each row has maximum \(2\). In row \(1\), that maximum occurs at column \(3\); in row \(2\), at column \(4\); in row \(3\), at column \(1\); and in row \(4\), at column \(2\). Therefore all four vertices have eccentricity \(2\), with \(F_G(1)=\{3\}\), \(F_G(2)=\{4\}\), \(F_G(3)=\{1\}\), and \(F_G(4)=\{2\}\).
Check: The nonadjacent pairs are \(1,3\) and \(2,4\). Each pair is connected by a two-edge route, and neither pair is an edge, so its distance is exactly \(2\). Every other distinct pair is an edge and has distance \(1\). This confirms the table and each row maximum.
Ties and Graph Structure
A farthest-vertex set need not have one element. A tie is not an ambiguity in the eccentricity: the row still has one largest numerical value, but several vertices attain it. The next example has ties in every row. Reading the complete set of column labels at the maximum is part of the calculation.
Worked Example: A Chorded Five-Cycle
Let \(G\) have \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45,51,13\}\). This is a five-cycle with an additional edge \(13\). To verify the distances, list the layers from each source. From \(1\), the layers are \(\{1\}\), \(\{2,3,5\}\), \(\{4\}\). From \(2\), they are \(\{2\}\), \(\{1,3\}\), \(\{4,5\}\). From \(3\), they are \(\{3\}\), \(\{1,2,4\}\), \(\{5\}\). From \(4\), they are \(\{4\}\), \(\{3,5\}\), \(\{1,2\}\). From \(5\), they are \(\{5\}\), \(\{1,4\}\), \(\{2,3\}\). These layers give the table:
| \(d(u,v)\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) |
|---|---|---|---|---|---|
| \(1\) | 0 | 1 | 1 | 2 | 1 |
| \(2\) | 1 | 0 | 1 | 2 | 2 |
| \(3\) | 1 | 1 | 0 | 1 | 2 |
| \(4\) | 2 | 2 | 1 | 0 | 1 |
| \(5\) | 1 | 2 | 2 | 1 | 0 |
Every row has maximum \(2\). In row \(1\), it occurs only at \(4\), so \(\operatorname{ecc}_G(1)=2\) and \(F_G(1)=\{4\}\). Row \(2\) attains \(2\) at \(4\) and \(5\), so \(\operatorname{ecc}_G(2)=2\) and \(F_G(2)=\{4,5\}\). Row \(3\) attains \(2\) only at \(5\), giving \(\operatorname{ecc}_G(3)=2\) and \(F_G(3)=\{5\}\). Row \(4\) attains \(2\) at \(1\) and \(2\), giving \(\operatorname{ecc}_G(4)=2\) and \(F_G(4)=\{1,2\}\). Row \(5\) attains \(2\) at \(2\) and \(3\), giving \(\operatorname{ecc}_G(5)=2\) and \(F_G(5)=\{2,3\}\).
Check: The layer lists show that all vertices are reached by distance \(2\) or less from every source, so no row maximum exceeds \(2\). Each row has at least one entry \(2\), so its maximum is not less than \(2\). The table is symmetric, as required for distances in this undirected graph.
Proof. An isomorphism is a bijection from \(V(G)\) to \(V(H)\) that preserves adjacency in both directions. Therefore it maps every path in \(G\) to a path of the same length in \(H\), and its inverse maps paths in \(H\) back to paths in \(G\). For corresponding vertices \(v\in V(G)\) and \(\phi(v)\in V(H)\), this means the shortest-path distances satisfy \(d_G(v,u)=d_H(\phi(v),\phi(u))\) for every \(u\in V(G)\): a shorter path on either side would map back to a shorter path on the other. As \(\phi\) is a bijection, the distances in the row of \(v\) and the row of \(\phi(v)\) have the same values, so their maxima are equal. The vertices attaining those maxima correspond under \(\phi\), which proves the assertion about farthest-vertex sets. \(\square\)
Common Pitfalls
Reporting only one farthest vertex. In the path example, row \(3\) has maximum \(2\) at both columns \(1\) and \(5\). Writing \(F_G(3)=\{1\}\) loses a vertex at the maximum. The correct set is \(\{1,5\}\), even though the eccentricity is still the single number \(2\).
Using a row minimum instead of its maximum. The diagonal entry is zero because a vertex has distance zero from itself. It is not the eccentricity unless the graph has just one vertex. For example, in the four-cycle, row \(1\) has minimum \(0\) and maximum \(2\); its eccentricity is \(2\), not \(0\).
Applying the definition to a disconnected graph without qualification. Here eccentricity is defined for vertices of a connected graph, where every distance is finite. If a graph is disconnected, some pairs have no path, so their distances are not finite under the usual distance convention. The connected-graph definition above cannot be applied unchanged to those rows.
Check Your Understanding
For each question, use the row maximum to find the eccentricity and include every column label attaining that maximum.
- For the path with \(V=\{a,b,c,d\}\) and \(E=\{ab,bc,cd\}\), find the eccentricity and farthest-vertex set of each vertex.
- A row of a distance table is \(0,1,2,2,1\), in columns \(a,b,c,d,e\). What are the eccentricity and farthest-vertex set for that row's vertex?
- Explain why a finite, connected graph with \(n\) vertices cannot have a distance greater than \(n-1\).
- If \(u\) and \(v\) are adjacent and \(\operatorname{ecc}_G(u)=4\), what upper bound does the adjacent-vertex proposition give for \(\operatorname{ecc}_G(v)\)? What lower bound does it give?
- In the one-vertex graph \(V=\{x\}\), \(E=\varnothing\), determine \(\operatorname{ecc}_G(x)\) and \(F_G(x)\).