In the graph below, N and M are most remote, and H is also an extremum.
Has the problem of finding the most remote vertices been formalized? Could you point me to publications or references on the subject? Does an algorithm exist for finding the most remote edges of a graph?
Please note that I am not asking you to invent an algorithm, but I'm asking for information.
One way to formulate your problem is well known as finding the diameter of a graph as the following description in Wikipedia.
The diameter $d$ d of a graph is the maximum eccentricity of any vertex in the graph. That is, $d$ is the greatest distance between any pair of vertices or, alternatively, $d=\max_{v\in V}\epsilon (v)$. To find the diameter of a graph, first find the shortest path between each pair of vertices. The greatest length of any of these paths is the diameter of the graph.
A peripheral vertex in a graph of diameter $d$ is one that is distance $d$ from some other vertex—that is, a vertex that achieves the diameter. Formally, $v$ is peripheral if $\epsilon (v)=d$.
Similarly to the way we talk about the diameter of a circle, the term "diameter of a graph" is overloaded. It can also mean, although less frequently, any shortest path between any two vertices whose length is equal to the maximum eccentricity.
If the graph is a tree, there is an algorithm that finds its diameter using only two BFS scans. Choose an arbitrary vertex $v$. Do a breadth first search from $v$ that finds a vertex that is farthest away from $v$. Call the vertex $u$. Do another BFS from $u$ that finds a vertex that is farthest away from $u$. Call the vertex $u'$. The distance between $u$ and $u'$ is the diameter of the graph.
In a general graph, many algorithms can be used to to find the diameter of a graph. Please check this CS StackExchange question and answer, where most algorithms are in fact designed to solve the all-pairs-shortest-path problem.
In the example graph given in the question, the distance between $N$ and $M$, 9, is the diameter. In fact, $N$ and $M$ are the only two peripheral vertices in that graph. (OP calls peripheral vertices as most remote). However, $H$ is not a peripheral vertex, since the furthest distance from any vertex to $H$ is only 8. ($H$ is not a pseudo-peripheral vertex, either.)
We could define an extremum of a graph as a vertex whose eccentricity is not smaller than the eccentricity of any of its neighbors. We could also define a strong extremum of a graph as a vertex whose distance to any vertex $v$ is not smaller than the distance from any of its neighbors to $v$. Every peripheral vertices is an extremum and every strong extremum is an extremum. We can recall a leaf vertex of a graph means a vertex of degree 1. Every leaf is a strong extremum. Note that $H$ is a leaf. All those algorithms that compute all-pairs-shortest-paths can be adapted easily to find all (strong) extremum vertices as well. A simple degree-counting algorithm will find all leaves of a graph. (Please note this definition of "extremum" might not be standard at all. As far as I have tried, I have not found a single article that defines that concept. Well, I can only check probably a negligible number of articles among a myriad of them. There is probably some existing term for it in papers about social network.)
