Simplified Constructions of almost Peripheral Graphs and Improved Embeddings into them

Abstract

The center and the periphery of a graph are the sets of vertices with minimum and maximum eccentricity, respectively. A graph is called almost peripheral (AP) if all its vertices but one lie in the periphery. The $r$-AP index ${\rm AP}_{r}(G)$ of a graph $G$ is the smallest number of vertices needed to add to $G$ to obtain an $r$-AP graph in which $G$ lies as an induced subgraph. In this paper new, simplified constructions of AP graphs are presented. It is proved that if $r\ge 2$ and $n\ge 2$, then $AP_r(K_n) \leq 4r-3$. Moreover, if $G$ is not complete and has at least three vertices, then $AP_r(G) \leq 4r-4$. In this way the previously best know bound $AP_r(G) \leq 4r-2$ is improved.