PDF
Discussiones Mathematicae Graph Theory 32(1) (2012)
19-29
DOI: https://doi.org/10.7151/dmgt.1582
Median of a Graph with Respect to Edges
| A.P. Santhakumaran
Department of Mathematics |
Abstract
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 d1(v) of v is d1(v) = ∑e ∈ Ed(v,e), the edge-to-vertex distance sum d2(e) of e is d2(e) = ∑v ∈ Vd(e,v) and the edge-to-edge distance sum d3(e) of e is d3(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 M1(G) of all vertices v for which d1(v) is minimum is the vertex-to-edge median of G; the set M2(G) of all edges e for which d2(e) is minimum is the edge-to-vertex median of G; and the set M3(G) of all edges e for which d3(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
2010 Mathematics Subject Classification: 05C12.
References
| [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. |
Received 4 June 2010
Revised 25 December 2010
Accepted 27 December 2010
Close