Geodesic
Median of a graph with respect to edges
Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 1, pp. 19-29.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: median, vertex-to-edge median, edge-to-vertex median, edge-to-edge median 
@article{DMGT_2012_32_1_a1,
     author = {Santhakumaran, A.},
     title = {Median of a graph with respect to edges},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {19--29},
     publisher = {mathdoc},
     volume = {32},
     number = {1},
     year = {2012},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2012_32_1_a1/}
}
TY  - JOUR
AU  - Santhakumaran, A.
TI  - Median of a graph with respect to edges
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2012
SP  - 19
EP  - 29
VL  - 32
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2012_32_1_a1/
LA  - en
ID  - DMGT_2012_32_1_a1
ER  - 
%0 Journal Article
%A Santhakumaran, A.
%T Median of a graph with respect to edges
%J Discussiones Mathematicae. Graph Theory
%D 2012
%P 19-29
%V 32
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2012_32_1_a1/
%G en
%F DMGT_2012_32_1_a1
Santhakumaran, A. Median of a graph with respect to edges. Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 1, pp. 19-29. http://geodesic.mathdoc.fr/item/DMGT_2012_32_1_a1/

[1] F. Buckley and F. Harary, Distance in Graphs (Addison-Wesley, Reading MA, 1990).

[2] F. Buckley, Z. Miller and P.J. Slater, On graphs containing a given graph as center, J. Graph Theory 5 (1981) 427-434, doi: 10.1002/jgt.3190050413.

[3] G. Chartrand and P. Zhang, Introduction to Graph Theory (Tata McGraw-Hill, New Delhi, 2006).

[4] L.C. Freeman, Centrality in Social networks; 1. Conceptual clarification, Social Networks 1 (1978/79) 215-239, doi: 10.1016/0378-8733(78)90021-7.

[5] C. Jordan, Sur les assemblages des lignas, J. Reine Angew. Math. 70 (1869) 185-190, doi: 10.1515/crll.1869.70.185.

[6] A.P. Santhakumaran, Center of a graph with respect to edges, SCIENTIA, Series A: Mathematical Sciences 19 (2010) 13-23.

[7] P.J. Slater, Some definitions of central structures, preprint.

[8] P.J. Slater, Centrality of paths and vertices in a graph : Cores and Pits, Theory and Applications of Graphs, ed, Gary Chartrand, (John Wiley, 1981) 529-542.

[9] B. Zelinka, Medians and Peripherians of trees, Arch. Math., Brno (1968) 87-95.