The Steiner Boundary Distance in Graphs

Abstract

For any two vertices u and v in a connected graph G, the distance d(u,v) between u and v is the length of a shortest path joining them. The eccentricity e(u) of a vertex u is the distance to a vertex farthest from u. A vertex v is an eccentric vertex of u if e(u) =d(u,v). It is clear that d(u,w) ≤ d(u,v) for all ) if v is an eccentric vertex of u. However, a vertex may have this property without being an eccentric vertex. A vertex v is a boundary vertex of a vertex u if d(u,w) ≤ d(u,v) for all . For a set S V(G), the Steiner distance d(S) is defined to be the minimum size of a connected subgraph containing S. We define B(u) as the set of all boundary vertices of u, and we call it as the boundary vertex set of u. The closed boundary vertex set of u is B[u]=B(u) U {u}. we define the Steiner–boundary distance dsb(u,v) between u and v is the minimum size of a connected subgraph containing B[u] U B[v]. The highlights of this paper are

1. Initiates a new distance parameter called Steiner-boundary


2. It follows the Nassi-Schneiderman style proof to prove the main