Median of a graph with respect to edges

Santhakumaran, A.

Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 1, pp. 19-29

Résumé

For any vertex v and any edge e in a non-trivial connected graph G, the distance sum d(v) of v is d(v) = ∑_u ∈ Vd(v,u), the vertex-to-edge distance sum d₁(v) of v is d₁(v) = ∑_e ∈ Ed(v,e), the edge-to-vertex distance sum d₂(e) of e is d₂(e) = ∑_v ∈ Vd(e,v) and the edge-to-edge distance sum d₃(e) of e is d₃(e) = ∑_f ∈ Ed(e,f). The set M(G) of all vertices v for which d(v) is minimum is the median of G; the set M₁(G) of all vertices v for which d₁(v) is minimum is the vertex-to-edge median of G; the set M₂(G) of all edges e for which d₂(e) is minimum is the edge-to-vertex median of G; and the set M₃(G) of all edges e for which d₃(e) is minimum is the edge-to-edge median of G. We determine these medians for some classes of graphs. We prove that the edge-to-edge median of a graph is the same as the median of its line graph. It is shown that the center and the median; the vertex-to-edge center and the vertex-to-edge median; the edge-to-vertex center and the edge-to-vertex median; and the edge-to-edge center and the edge-to-edge median of a graph are not only different but can be arbitrarily far apart.

Détail

Keywords: median, vertex-to-edge median, edge-to-vertex median, edge-to-edge median