This is a graph
Node B is a pivotal node.
It provides the shortest path to get from A to C and A to D.
Pivotal is Relative.
Node B is NOT pivotal for D and F because because there is another shortest path they can take.
Some Nodes are Never Pivotal.
Also note D is not pivatol for any pairs.
Here's Another Graph.
Gatekeeper
Node A is a gatekeeper because it lies on every path from E to B.Gatekeeper is Relative to Scale.
Node B is a local gatekeeper because it connects nodes C and D
But B is not a global gatekeeper because C and D can also be connected through A.
One More Graph
Graph Length
The number of edges within the entire graph
Graph Distance
The distance between two vertices in a graph is the number of edges in their shortest path. The matrix shows the minimum distance between every node
A | B | C | F | G | E | D | |
A | 0 | 1 | 1 | 1 | 2 | 1 | 2 |
B | 1 | 0 | 1 | 2 | 3 | 2 | 3 |
C | 1 | 1 | 0 | 1 | 3 | 2 | 3 |
F | 1 | 2 | 1 | 0 | 2 | 1 | 2 |
G | 2 | 3 | 3 | 2 | 0 | 1 | 2 |
E | 1 | 2 | 2 | 1 | 1 | 0 | 1 |
D | 2 | 3 | 3 | 2 | 2 | 1 | 0 |
Eccentricity
Let's look at Node A, the first row in our matrix.
The path from A to B, C, F, & E is 1, and to G or D is 2.
The highest shortest path length of A [its eccentricitiy] is 2.
Diameter
While eccentricity is a metric we can apply to every node, the graph's diameter is the maximum overall distance of every pair of nodes in the graph.
Radius: Periheral
The radius is the minimum eccentricity of the graph.
Any vertex whose eccentricity is equal to the graph's diameter is peripheral.
Radius: Central
If the eccentricity of a node is equal to the graphs radius then it is a central vertex
As we can see here, the radius of a graph is always less than the diameter which always less than 2 times the diameter of the graph.
$$\text{rad}(G) \leq \text{diam}(G) \leq 2 \text{ rad}(G) $$
The first inequality, that the minimum eccentricities (2) is smaller than the maximum eccentricities (3) is logical.
We can prove the second inequality by looking at 2 peripheral nodes, G and B, and one central node, A.
We know the diameter is the distance from G to B.
We also know that distance is bounded by the distance from G to A (at most A's accentricity = 2) and A to B (at most A's accentricity = 2).
We also know A's accentricity is the radius because it is a central node. Therefore:
$$d(u,v) \leq 2*rad(G)$$