Bounding the boundary by the minimum and maximum degree
Tobias Müller, Attila Pór, J.-S. Sereni · TU/e Research Portal · 2007
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 the best possible lower bound, up to a constant factor, on the number of boundary vertices of a graph in terms of its minimum degree (or maximum degree).This settles a problem introduced by Hasegawa and Saito.