Lower bounding the boundary of a graph in terms of its maximum or minimum degree

Abstract: A vertex of a graph is a boundary vertex if there exists a vertex such that the distance in from to is at least the distance from to any neighbour of . 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. [Copyright &y& Elsevier]