Graphs with four boundary vertices (Q625373)

Summary: A vertex \(v\) of a graph \(G\) is a boundary vertex if there exists a vertex u such that the distance in \(G\) from \(u\) to \(v\) is at least the distance from \(u\) to any neighbour of \(v\). We give a full description of all graphs that have exactly four boundary vertices, which answers a question of Hasegawa and Saito. To this end, we introduce the concept of frame of a graph. It allows us to construct, for every positive integer \(b\) and every possible ``distance-vector'' between \(b\) points, a graph \(G\) with exactly \(b\) boundary vertices such that every graph with \(b\) boundary vertices and the same distance-vector between them is an induced subgraph of \(G\).