The Exterior of a Graph or Tree

Abstract

The eccentricity \(e(v)\) of a vertex \(v\) in a connected graph \(G\) is the distance between \(v\) and a vertex furthest from \(v\). The center \(C(G)\) is the subgraph induced by those vertices whose eccentricity is the radius of \(G\), denoted \(\mathrm{rad}G\), and the periphery \(P(G)\) is the subgraph induced by those vertices with eccentricity equal to the diameter of \(G\), denoted \(\mathrm{diam}G\). The annulus \(\mathrm{Ann}(G)\) is the subgraph induced by those vertices with eccentricities strictly between the radius and diameter of \(G\). In a graph \(G\) where \(\mathrm{rad}G < \mathrm{diam}G\), the interior of \(G\) is the subgraph \(\mathrm{Int}(G)\) induced by the vertices \(v\) with \(e(v) < \mathrm{diam}G\). Otherwise, if \(\mathrm{rad}G = \mathrm{diam}G\), then \(\mathrm{Int}(G) = G\). Another subgraph for a connected graph \(G\) with \(\mathrm{rad}G < \mathrm{diam}G\), called the exterior of \(G\), is defined as the subgraph \(\mathrm{Ext}(G)\) induced by the vertices \(v\) with \(\mathrm{rad}G < e(v)\). As with the interior, if \(\mathrm{rad}G = \mathrm{diam}G\), then \(\mathrm{Ext}(G) = G\). In this paper, the annulus, interior, and exterior subgraphs in trees are characterized.