Boundary vertices in graphs Original Research Article

The distance d(u,v) between two vertices u and v in a nontrivial connected graph G is the length of a shortest u–v path in G. For a vertex v of G, the eccentricity e(v) is the distance between v and a vertex farthest from v. A vertex v of G is a peripheral vertex if e(v) is the diameter of G. The subgraph of G induced by its peripheral vertices is the periphery Per(G) of G. A vertex u of G is an eccentric vertex of a vertex v if d(u,v)=e(v). A vertex x is an eccentric vertex of G if x is an eccentric vertex of some vertex of G. The subgraph of G induced by its eccentric vertices is the eccentric subgraph Ecc(G) of G. A vertex u of G is a boundary vertex of a vertex v if d(w,v)⩽d(u,v) for all w∈N(u). A vertex u is a boundary vertex of G if u is a boundary vertex of some vertex of G. The subgraph of G induced by its boundary vertices is the boundary ∂(G) of G. A graph H is a boundary graph if H=∂(G) for some graph G. We study the relationship among the periphery, eccentric subgraph, and boundary of a connected graph and establish a characterization of all boundary graphs. It is shown that for each triple a,b,c of integers with 2⩽a⩽b⩽c, there is a connected graph G such that Per(G) has order a, Ecc(G) has order b, and ∂(G) has order c. Moreover, for each triple r,s,t of rational numbers with 0