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 θ_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 θ_r(G) ≤ 2 r holds for any graph G and any r≥ 2 which improves the earlier known bound θ_r(G) ≤ 2 r+ 1. It is further proved that θ_r(G) ≤ 2 r- 1 holds if r≥ 3 and G is of order at least 2. The 3-ASC index of complete graphs is determined. It is proved that θ₃(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 θ₃(G) = 4. The 3-ASC index of paths of order n≥ 1 , cycles of order n≥ 3 , and trees of order n≥ 10 and diameter n- 2 are also determined, respectively, and several open problems proposed.