کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4651003 1342515 2007 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Graphs with small boundary
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Graphs with small boundary
چکیده انگلیسی

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)|.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 307, Issue 14, 28 June 2007, Pages 1801–1807
نویسندگان
, ,