- Tytuł:
- The Median Problem on k-Partite Graphs
- Autorzy:
-
Pravas, Karuvachery
Vijayakumar, Ambat - Powiązania:
- https://bibliotekanauki.pl/articles/31339417.pdf
- Data publikacji:
- 2015-08-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
networks
distance
median
bipartite
k-partite - Opis:
- 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
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2015, 35, 3; 439-446
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł