کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4651003 | 1342515 | 2007 | 7 صفحه PDF | دانلود رایگان |

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)|.
Journal: Discrete Mathematics - Volume 307, Issue 14, 28 June 2007, Pages 1801–1807