# The Median Problem on k-Partite Graphs

Karuvachery Pravas; Ambat Vijayakumar

Discussiones Mathematicae Graph Theory (2015)

- Volume: 35, Issue: 3, page 439-446
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topKaruvachery Pravas, and Ambat Vijayakumar. "The Median Problem on k-Partite Graphs." Discussiones Mathematicae Graph Theory 35.3 (2015): 439-446. <http://eudml.org/doc/271223>.

@article{KaruvacheryPravas2015,

abstract = {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},

author = {Karuvachery Pravas, Ambat Vijayakumar},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {networks; distance; median; bipartite; k-partite.; -partite},

language = {eng},

number = {3},

pages = {439-446},

title = {The Median Problem on k-Partite Graphs},

url = {http://eudml.org/doc/271223},

volume = {35},

year = {2015},

}

TY - JOUR

AU - Karuvachery Pravas

AU - Ambat Vijayakumar

TI - The Median Problem on k-Partite Graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2015

VL - 35

IS - 3

SP - 439

EP - 446

AB - 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

LA - eng

KW - networks; distance; median; bipartite; k-partite.; -partite

UR - http://eudml.org/doc/271223

ER -

## References

top- [1] K. Balakrishnan, B. Brešar, M. Kovše, M. Changat, A.R. Subhamathi and S. Klavžar, Simultaneous embeddings of graphs as median and antimedian ubgraphs, Networks 56 (2010) 90-94. doi:10.002/net.20350[WoS] Zbl1207.05037
- [2] R. Balakrishnan and K. Ranganathan, A Textbook of Graph Theory, Second Edition (Heidelberg, Springer, 2012). doi:10.1007/978-1-4614-4529-6[Crossref] Zbl1254.05001
- [3] H. Bielak and M.M. Sys lo, Peripheral vertices in graphs, Studia Sci. Math. Hungar. 18 (1983) 269-275. Zbl0569.05030
- [4] H. Kautz, B. Selman and M. Shah, Referral Web: combining social networks and collaborative filtering, Communications of the ACM 40(3) (1997) 63-65. doi:10.1145/245108.245123[Crossref]
- [5] K. Pravas and A. Vijayakumar, Convex median and anti-median at pre- scribed distance, communicated.
- [6] P.J. Slater, Medians of arbitrary graphs, J. Graph Theory 4 (1980) 389-392. doi:10.1002/jgt.3190040408[Crossref] Zbl0446.05029
- [7] S.B. Rao and A.Vijayakumar, On the median and the anti-median of a co- graph, Int. J. Pure Appl. Math. 46 (2008) 703-710. Zbl1171.05014
- [8] H.G. Yeh and G.J. Chang, Centers and medians of distance-hereditary graphs, Discrete Math. 265 (2003) 297-310. doi:10.1016/S0012-365X(02)00630-1 [Crossref] Zbl1026.05035

## NotesEmbed ?

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