I was doing following construction. We know $C_4$ and $C_5$ are $2$-self-centered graphs. When we add a new vertex $x$ and $y$ to $C_4$ and $C_5$, resp, (shown in fig) the new graph contains exactly two vertices with eccentricity three and rest with eccentricity two. I was curious to know if we propose a similar construction where eccentricity of every vertex is three and only one vertex with ecc two, using the same graphs $C_4$ and $C_5$. By adding one or two vertices such that resultant graphs contain $C_4$ and $C_5$ and as induced subgraphs. Any hint will be appreciated. Thanks a lot.
Note : A self-centered graph is a graph where eccentricity of every vertex is the same.
We seek a graph $G$ with the desired eccentricities and containing $C_5$ as an induced subgraph. Start with the induced $C_5$ subgraph and add one vertex. Clearly, $G$ must be connected, and there is only one way to add an edge to connect the new vertex, up to isomorphism.
The vertices of eccentricity $2$ are circled. Because additional edges cannot decrease eccentricity and the graph has too many vertices of eccentricity $2$, the single extra vertex is insufficient. Add a second vertex. We again add an edge for connectivity, and there are four non-isomorphic ways to do so.
With reasoning similar to before, the top two graphs will not suffice. The bottom two graphs have vertices with eccentricity $4$, so additional edges are necessary, but it can be checked that no edge may be added (keeping the $C_5$ induced) without creating an additional vertex with eccentricity $2$, so neither graph suffices. Therefore, at least $3$ additional vertices are necessary.
Below left is a graph with $C_5$ as an induced subgraph and $3$ added vertices such that the circled vertex has eccentricity $2$ and every other vertex has eccentricity $3$, satisfying the desired properties. In a similar way, it can be shown that $3$ vertices must be added to $C_4$ to satisfy the desired properties, and the graph below right shows that $3$ suffice.