Nonmedian Direct Products of Graphs with Loops

Abstract

A median graph is a connected graph in which, for every three vertices, there exists a unique vertex $m$ lying on the geodesic between any two of the given vertices. We show that the only median graphs of the direct product $G\times H$ are formed when $G=P_k$, for any integer $k\ge 3$, and $H=P_l$, for any integer $l\ge 2$, with a loop at an end vertex, where the direct product is taken over all connected graphs $G$ on at least three vertices or at least two vertices with at least one loop, and connected graphs $H$ with at least one loop.