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

Abstract

top
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

How to cite

top

Karuvachery 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. [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. [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. [3] H. Bielak and M.M. Sys lo, Peripheral vertices in graphs, Studia Sci. Math. Hungar. 18 (1983) 269-275. Zbl0569.05030
  4. [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. [5] K. Pravas and A. Vijayakumar, Convex median and anti-median at pre- scribed distance, communicated. 
  6. [6] P.J. Slater, Medians of arbitrary graphs, J. Graph Theory 4 (1980) 389-392. doi:10.1002/jgt.3190040408[Crossref] Zbl0446.05029
  7. [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. [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 ?

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.