Median of a graph with respect to edges

• Volume: 32, Issue: 1, page 19-29
• ISSN: 2083-5892

top

Abstract

top
For any vertex v and any edge e in a non-trivial connected graph G, the distance sum d(v) of v is $d\left(v\right)={\sum }_{u\in V}d\left(v,u\right)$, the vertex-to-edge distance sum d₁(v) of v is $d₁\left(v\right)={\sum }_{e\in E}d\left(v,e\right)$, the edge-to-vertex distance sum d₂(e) of e is $d₂\left(e\right)={\sum }_{v\in V}d\left(e,v\right)$ and the edge-to-edge distance sum d₃(e) of e is $d₃\left(e\right)={\sum }_{f\in E}d\left(e,f\right)$. 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.

How to cite

top

A.P. Santhakumaran. "Median of a graph with respect to edges." Discussiones Mathematicae Graph Theory 32.1 (2012): 19-29. <http://eudml.org/doc/270947>.

@article{A2012,
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 ∈ V\}d(v,u)$, the vertex-to-edge distance sum d₁(v) of v is $d₁(v) = ∑_\{e ∈ E\}d(v,e)$, the edge-to-vertex distance sum d₂(e) of e is $d₂(e) = ∑_\{v ∈ V\}d(e,v)$ and the edge-to-edge distance sum d₃(e) of e is $d₃(e) = ∑_\{f ∈ E\}d(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.},
author = {A.P. Santhakumaran},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {median; vertex-to-edge median; edge-to-vertex median; edge-to-edge median},
language = {eng},
number = {1},
pages = {19-29},
title = {Median of a graph with respect to edges},
url = {http://eudml.org/doc/270947},
volume = {32},
year = {2012},
}

TY - JOUR
AU - A.P. Santhakumaran
TI - Median of a graph with respect to edges
JO - Discussiones Mathematicae Graph Theory
PY - 2012
VL - 32
IS - 1
SP - 19
EP - 29
AB - 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 ∈ V}d(v,u)$, the vertex-to-edge distance sum d₁(v) of v is $d₁(v) = ∑_{e ∈ E}d(v,e)$, the edge-to-vertex distance sum d₂(e) of e is $d₂(e) = ∑_{v ∈ V}d(e,v)$ and the edge-to-edge distance sum d₃(e) of e is $d₃(e) = ∑_{f ∈ E}d(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.
LA - eng
KW - median; vertex-to-edge median; edge-to-vertex median; edge-to-edge median
UR - http://eudml.org/doc/270947
ER -

References

top
1. [1] F. Buckley and F. Harary, Distance in Graphs (Addison-Wesley, Reading MA, 1990). Zbl0688.05017
2. [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. Zbl0449.05056
3. [3] G. Chartrand and P. Zhang, Introduction to Graph Theory (Tata McGraw-Hill, New Delhi, 2006). Zbl1096.05001
4. [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. [5] C. Jordan, Sur les assemblages des lignas, J. Reine Angew. Math. 70 (1869) 185-190, doi: 10.1515/crll.1869.70.185.
6. [6] A.P. Santhakumaran, Center of a graph with respect to edges, SCIENTIA, Series A: Mathematical Sciences 19 (2010) 13-23. Zbl1244.05081
7. [7] P.J. Slater, Some definitions of central structures, preprint. Zbl0545.05039
8. [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. [9] B. Zelinka, Medians and Peripherians of trees, Arch. Math., Brno (1968) 87-95. Zbl0206.26105

NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.