Geodesic
The Median Problem on k-Partite Graphs
Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 3, pp. 439-446

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

In a connected graph G, the status of a vertex is the sum of the distances of that vertex to each of the other vertices in G. The subgraph induced by the vertices of minimum (maximum) status in G is called the median (anti-median) of G. The median problem of graphs is closely related to the optimization problems involving the placement of network servers, the core of the entire networks. Bipartite graphs play a significant role in designing very large interconnection networks. In this paper, we answer a problem on the structure of medians of bipartite graphs by showing that any bipartite graph is the median (or anti-median) of another bipartite graph. Also, with a different construction, we show that the similar results hold for k-partite graphs, k ≥ 3. In addition, we provide constructions to embed another graph as center in both bipartite and k-partite cases. Since any graph is a k-partite graph, for some k, these constructions can be applied in general
Keywords: networks, distance, median, bipartite, k-partite 
@article{DMGT_2015_35_3_a3,
     author = {Pravas, Karuvachery and Vijayakumar, Ambat},
     title = {The {Median} {Problem} on {k-Partite} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {439--446},
     publisher = {mathdoc},
     volume = {35},
     number = {3},
     year = {2015},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2015_35_3_a3/}
}
TY  - JOUR
AU  - Pravas, Karuvachery
AU  - Vijayakumar, Ambat
TI  - The Median Problem on k-Partite Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2015
SP  - 439
EP  - 446
VL  - 35
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2015_35_3_a3/
LA  - en
ID  - DMGT_2015_35_3_a3
ER  - 
%0 Journal Article
%A Pravas, Karuvachery
%A Vijayakumar, Ambat
%T The Median Problem on k-Partite Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2015
%P 439-446
%V 35
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2015_35_3_a3/
%G en
%F DMGT_2015_35_3_a3
Pravas, Karuvachery; Vijayakumar, Ambat. The Median Problem on k-Partite Graphs. Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 3, pp. 439-446. http://geodesic.mathdoc.fr/item/DMGT_2015_35_3_a3/