Graphs with four boundary vertices
The electronic journal of combinatorics, Tome 18 (2011) no. 1
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$.
DOI :
10.37236/498
Classification :
05C75, 05C12
Mots-clés : boundary vertex, distance vector, frame of a graph
Mots-clés : boundary vertex, distance vector, frame of a graph
@article{10_37236_498,
author = {Tobias M\"uller and Attila P\'or and Jean-S\'ebastien Sereni},
title = {Graphs with four boundary vertices},
journal = {The electronic journal of combinatorics},
year = {2011},
volume = {18},
number = {1},
doi = {10.37236/498},
zbl = {1205.05194},
url = {http://geodesic.mathdoc.fr/articles/10.37236/498/}
}
Tobias Müller; Attila Pór; Jean-Sébastien Sereni. Graphs with four boundary vertices. The electronic journal of combinatorics, Tome 18 (2011) no. 1. doi: 10.37236/498
Cité par Sources :