Characterization of the Cartesian product of complete graphs by convex subgraphs (Q1076038)

An induced subgraph \(H\) of a graph \(G\) is said to be convex if for any two nodes \(x, y\) in \(H\), \(H\) contains all paths joining \(x\) and \(y\) in \(G\) with minimum length. \(H\) is called proper convex if it is convex and neither the empty graph nor \(G\) itself. It is shown that a graph \(G\) must have at least \(n^ r\) nodes provided \(G\) is connected and has the same proper convex subgraphs as \((K_ n)^ r\), the Cartesian product of \(r\) copies of \(K_ r\), \(r\geq 2\), \(n\geq 3\). \(G\) has precisely \(n^ r\) nodes if it is isomorphic to \((K_ n)^ r\).