Article ID Journal Published Year Pages File Type
4651003 Discrete Mathematics 2007 7 Pages PDF
Abstract

For a pair of vertices x and y in a graph G  , we denote by dG(x,y)dG(x,y) the distance between x and y in G. We call x a boundary vertex of y if x and y   belong to the same component and dG(y,v)⩽dG(y,x)dG(y,v)⩽dG(y,x) for each neighbor vv of x in G. A boundary vertex of some vertex is simply called a boundary vertex, and the set of boundary vertices in G is called the boundary of G  , and is denoted by B(G)B(G).In this paper, we investigate graphs with a small boundary. Since a pair of farthest vertices are boundary vertices, |B(G)|⩾2|B(G)|⩾2 for every connected graph G of order at least two. We characterize the graphs with boundary of order at most three. We cannot give a characterization of graphs with exactly four boundary vertices, but we prove that such graphs have minimum degree at most six. Finally, we give an upper bound to the minimum degree of a connected graph G   in terms of |B(G)||B(G)|.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,