Talk:Distance (graph theory)

diameter in disconnected graphs

what happens to diameter if the graph is not connected? — Preceding unsigned comment added by Sigmundur (talk • contribs) 13:25, 18 November 2006 (UTC)[reply]

This question apparently got an answer in the #Is eccentricity in disconnected graphs infinite? section below. --CiaPan (talk) 11:50, 23 January 2020 (UTC)[reply]

pseudo-peripheral vertices in directed graphs ?

Does the given "Algorithm for finding pseudo-peripheral vertices" work also in directed graphs? If yes, do I need to use indegree or outdegree? If not, it should be mentioned that the algorithm is only for undirected graphs. 80.248.242.52 18:14, 26 December 2006 (UTC)[reply]

asymptotics?

How do we know that peripheral vertices are hard to find? What is the asymptotic running time for the best algorithm to find a peripheral vertex? What is the asymptotic running time for the pseudo-peripheral vertex finding algorithm described in the text? 89.132.107.235 (talk) 20:52, 26 February 2008 (UTC)[reply]

Name

Why does the article use the term "geodetic distance"? The usual name is simply "distance". Zaslav (talk) 02:24, 27 October 2015 (UTC)[reply]

Graph theorists say "distance" but people from other parts of mathematics or physics, etc., sometime use "geodesic distance" or "geodetic distance". It seems reasonable to mention it. McKay (talk) 03:02, 29 October 2015 (UTC)[reply]

Is eccentricity in disconnected graphs infinite?

Am I right with thinking that the $\max$ operator in the eccentricity definition (and, as a result, in definitions of radius and diameter and the rest) includes infinite distances for disconnected graphs? That looks reasonable, because otherwise the measures would be automatically defined separately for each connected components. On the other hand, that implies that in disconnected graphs (just one not connected vertex is enough):

all nodes have infinite eccentricity,
so the graph has infinite radius & diameter,
there are no central vertices (infinities are hardly comparable, so no one vertex has the least eccentricity)
or all vertices become central (all infinities are equal, hence are minimal)

– but that looks weird and disgusting. --CiaPan (talk) 10:41, 22 January 2020 (UTC)[reply]

From what I can find online, most authors, including Frank Harary, who, if anyone, should be taken as the final arbiter on graph theory, only define eccentricity for connected graphs. As you point out, the definition can be extended to disconnected graphs, but, as you also point out, it gives infinite eccentricity for all nodes, which is hardly useful. It seems vague where the article falls on whether eccentricity is defined for disconnected graphs, but considering Harary is used as a reference, I'd say it should be clarified in the 'no' direction. --RDBury (talk) 13:41, 22 January 2020 (UTC)[reply]

Metric Space in Disconnected Graph

Why do the vertex set (of an undirected graph) and the distance function form a metric space if and only if the graph is connected? The distance between disconnected vertices is ∞ as defined in the article, and there are metric spaces which allow for infinite distance. It seems this should still obey the necessary axioms of a metric space for disconnected graphs. Erythrochroism (talk) 16:32, 16 May 2022 (UTC)[reply]

@Erythrochroism: That would be an extended metric – see Metric (mathematics) § Extended metrics. --CiaPan (talk) 21:02, 16 May 2022 (UTC)[reply]