Antimedian graphs

Antimedian graphs are introduced as the graphs in which for every triple of vertices there exists a unique vertex x that maximizes the sum of the distances from x to the vertices of the triple. The Cartesian product of graphs is antimedian if and only if its factors are antimedian. It is proved that multiplying a non-antimedian vertex in an antimedian graph yields a larger antimedian graph. Thin even belts are introduced and proved to be antimedian. A characterization of antimedian trees is given that leads to a linear recognition algorithm.

Cochin University of Science and Technology ,Ministry of Science of Slovenia and by the Ministry of Science and Technology of India