Embeddings into almost self-centered graphs of given radius

A graph is almost self-centered (ASC) if all but two of its vertices are central. An almost self-centered graph with radius r is called an r-ASC graph. The r-ASC index $$\theta _r(G)$$ θ r ( G ) of a graph G is the minimum number of vertices needed to be added to G such that an r-ASC graph is obtained that contains G as an induced subgraph. It is proved that $$\theta _r(G)\le 2r$$ θ r ( G ) ≤ 2 r holds for any graph G and any $$r\ge 2$$ r ≥ 2 which improves the earlier known bound $$\theta _r(G)\le 2r+1$$ θ r ( G ) ≤ 2 r + 1 . It is further proved that $$\theta _r(G)\le 2r-1$$ θ r ( G ) ≤ 2 r - 1 holds if $$r\ge 3$$ r ≥ 3 and G is of order at least 2. The 3-ASC index of complete graphs is determined. It is proved that $$\theta _3(G)\in \{3,4\}$$ θ 3 ( G ) ∈ { 3 , 4 } if G has diameter 2 and for several classes of graphs of diameter 2 the exact value of the 3-ASC index is obtained. For instance, if a graph G of diameter 2 does not contain a diametrical triple, then $$\theta _3(G) = 4$$ θ 3 ( G ) = 4 . The 3-ASC index of paths of order $$n\ge 1$$ n ≥ 1 , cycles of order $$n\ge 3$$ n ≥ 3 , and trees of order $$n\ge 10$$ n ≥ 10 and diameter $$n-2$$ n - 2 are also determined, respectively, and several open problems proposed.