Graphs with Four Boundary Vertices

  • Tobias Müller
  • Attila Pór
  • Jean-Sébastien Sereni


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$.

Article Number