1- The distance between any two vertices u and v, denoted d(u, v), is the length of a shortest u − v path, also called a u − v geodesic.
2- Suppose G is a (weighted) graph and S a set of vertices in G. Then the Steiner distance for S, denoted by d_G(S), is the smallest weight of a connected subgraph of G containing S. Such a subgraph is necessarily a tree, called a Steiner tree for S. The radius, diameter and average distance have a natural extension. For a given vertex v in a connected (weighted) graph G and integer k (2 ≤ k ≤ n), the k-eccentricity of v, denoted by e_k(v), is the maximum Steiner distance among all k-sets of vertices in G that contain v. The k-radius, rad_k(G), of G is the minimum k-eccentricity of the vertices of G, and the k-diameter, diam_k(G), of G is the maximum k-eccentricity
we have many distances, detour is an example. detour means the length of the longest path between u and v
what about the distance between two edges in graph, which defined by the
number of vertices in the shortest path containing them minus two.
Could your edges possibly be colored? If so, there are several notions of colored connectivity (and corresponding distances) in the attached publications.
Are you focused on a fixed graph or might you consider distance between graphs? Then the edit-distance might suit your purposes. See the attached publication "On Distance Between Graphs" and its citations for example.
Article Proper connection of graphs
Article Rainbow Connections of Graphs: A Survey
Article On Distance Between Graphs
Article Properly Colored Notions of Connectivity - A Dynamic Survey
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs