# A question regarding construction of a graph.

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.

• What makes a vertex eccentrjc? Commented Mar 31, 2018 at 8:05
• The maximum distance between a vertex to all other vertices is considered as the eccentricity of vertex. The distance from a particular vertex to all other vertices in the graph is taken and among those distances, the eccentricity is the highest of distances Commented Mar 31, 2018 at 10:15
• Are there selfcentered graphs that are not circuits? Commented Mar 31, 2018 at 10:31
• complete graphs, cartesian product of self centered graphs are some examples. Commented Mar 31, 2018 at 10:57
• The addition of edges cannot increase eccentricities. Commented Mar 31, 2018 at 16:49

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.
• Can we do the same for the graph $C_6$? I tried using this scheme by adding three vertices. But I am getting all vertices with eccentricity four and three with eccentricity 3. I want only one vertex with ecc 3 and rest with ecc 4. It is like some kind of generalisation. I will be thankful to you a lot. Commented Apr 3, 2018 at 4:46
• A similar construction works in that case, but $5$ added vertices are necessary. Commented Apr 3, 2018 at 18:40