Distance-residual graphs

Abstract

If we are given a connected finite graph $G$ and a subset of its vertices $V_0$, we define a distance-residual graph as a graph induced on the set of vertices that have the maximal distance from $V_0$. Some properties and examples of distance-residual graphs of vertex-transitive, edge-transitive, bipartite and semisymmetric graphs are shown. The relations between the distance-residual graphs of product graphs and their factors are shown.

14 pages, 4 figures