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.

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