Boundary-type sets in maximal outerplanar graphs

Abstract The periphery Per( G ) of a graph G is the set of vertices of maximum eccentricity. A vertex v belongs to the contour Ct( G ) of G if no neighbor of v has an eccentricity greater than the eccentricity of v . The extreme set Ext( G ) of G is the set of all its simplicial (also called extreme) vertices; an extreme vertex is such that its neighborhood induces a complete graph. The eccentricity Ecc( G ) of a graph G is the set of all its eccentric vertices, i.e. vertices that are antipodal to some other vertex in G . A vertex v is a boundary vertex if there is another vertex u in G such that no u - v geodesic can be extended at v to a longer geodesic. The boundary ∂ ( G ) of G is the set of all its boundary vertices. For the family of maximal outerplanar graphs, we provide a characterization of ∂ ( G ) and Ext ( G ) in terms of vertex degrees. We characterize those graphs that are induced by Per( G ) and Ct( G ). We show that, unlike for trees, all relationships between boundary-type sets in maximal outerplanar graphs are as rich as in general graphs and we construct a single maximal outerplanar graph showing the sharpness of all those inclusions.