Boundary vertices in graphs

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 it of G is an eccentric vertex of a vertex v if d(u, v) = e(u). 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 it of G is a boundary vertex of a vertex v if d(w, v) less than or equal to d(u, v) for all w is an element of 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 partial derivative(G) of G. A graph H is a boundary graph if H = partial derivative(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 less than or equal to a less than or equal to b less than or equal to 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 < r less than or equal to s less than or equal to t less than or equal to 1, there is a connected graph G of order n such that \V(Per(G))\/n = r, \V(Ecc(G))\/n = s, and \V(partial derivative(G))\/n = t. (C) 2002 Elsevier Science B.V. All rights reserved.