Skip to main content
To KTH's start page To KTH's start page

Sandhya Thekkumpadan Puthiyaveedu: k-Median Graphs

Time: Wed 2022-10-19 13.30

Location: Albano, Cramer room

Participating: Sandhya Thekkumpadan Puthiyaveedu

Export to calendar


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.