Menu
A vertex \( v \) of a connected graph \( G \) is an eccentric vertex of a vertex \( u \) if \( v \) is a vertex at greatest distance from \( u \); while \( v \) is an eccentric vertex of \( G \) if \( v \) is an eccentric vertex of some vertex of \( G \). The subgraph of \( G \) induced by its eccentric vertices is the eccentric subgraph of \( G \).
A vertex \( v \) of \( G \) is a boundary vertex of a vertex \( u \) if \( d(u,w) \leq d(u,v) \) for each neighbor \( w \) of \( v \). A vertex \( v \) is a boundary vertex of \( G \) if \( v \) is a boundary vertex of some vertex of \( G \). The subgraph of \( G \) induced by its boundary vertices is the boundary of \( G \). A vertex \( v \) is an interior vertex of \( G \) if for every vertex \( u \) distinct from \( v \), there exists a vertex \( w \) distinct from \( v \) such that \( d(u,w) = d(u,v) + d(v,w) \). The interior of \( G \) is the subgraph of \( G \) induced by its interior vertices. A vertex \( v \) is a boundary vertex of a connected graph if and only if \( v \) is not an interior vertex. For every graph \( G \), there exists a connected graph \( H \) such that \( G \) is both the center and interior of \( H \).
Relationships between the boundary and the periphery, center, and eccentric subgraph of a graph are studied. The boundary degree of a vertex \( v \) in a connected graph \( G \) is the number of vertices \( u \) in \( G \) having \( v \) as a boundary vertex. We study, for each pair \( r,n \) of integers with \( r \geq 0 \) and \( n \geq 3 \), the existence of a connected graph \( G \) of order \( n \) such that every vertex of \( G \) has boundary degree \( r \). We also study the boundary vertices of a connected graph from different points of view.