# zbMATH — the first resource for mathematics

Antimedian graphs. (English) Zbl 1201.05029
Summary: 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.

##### MSC:
 05C12 Distance in graphs 05C76 Graph operations (line graphs, products, etc.)