Sandhya Thekkumpadan Puthiyaveedu: k-Median Graphs

Abstract

A connected graph is a median graph if it satisfies the following property: for every triplet (x,y,z) of vertices, there exists a unique vertex that is contained in the shortest paths between every pair of x, y and z. Median graphs have been studied at least since the 1940's. Median graphs naturally arise in several fields of mathematics, for example, in algebra, metric graph theory and geometry, and they have practical applications in areas such as social choice theory, phylogenetics and forensic science. We generalize the concept of median graphs to the class of k-median graphs where k denotes the number of so-called median vertices present in a particular graph. In particular, median graphs G are precisely the |V(G)|-median graphs. We give first structural insights into this novel concept.