# To construct a graph with desired eccentricity.

I am trying to solve a problem.

$G$ is a graph where eccentricity of vertices $x$ and $y$ is $8$, and rest of the vertices have eccentricity $7$. Also $d(x,y) = 8$. I am trying to make eccentricities of $x$ and $y$ also $7$ by adding a vertex (or two vertices). The old graph must be induced in new graph. I proposed a construction:

Let $w$ be any vertex in $G$ such that $d(y,w) = 3$. Add a new vertex $z$ and make it adjacent to $y$ and $w$.

Is this true that every vertex in this new graph will have eccentricity $7$? For a few examples, I got the desired result. Or is there any other way to construct this(by adding one more vertex)?

PS: As asked by @bof, I tried for a smaller value. Like in the following figure, two vertices have eccentricity three and rest have eccentricity two, I tried to make eccentricity of every as two by adding a new vertex. As required the old graph is induced in new graph. • The eccentricity of a graph vertex in a connected graph is the maximum graph distance between and any other vertex of. Jun 10, 2018 at 15:19
• I have a definition of eccentricity only on trees, what is the definition on graphs, for example if I have $K_4$ how eccentricity of each vertex? Jun 10, 2018 at 21:04
• Since for an arbitrary vertex $x$ in $K_4$, the maximum distance between $x$ and other vertices is one, hence eccentricity is one for every vertex of $K_4$ and hence for every complete graph. See this link will help you. :) tutorialspoint.com/graph_theory/… Jun 11, 2018 at 3:30
• Are you sure this can be done? Was this given as an exercise?
– bof
Jun 11, 2018 at 7:39
• Yeah, it is an exercise. Prove or disprove type. Jun 11, 2018 at 8:20

It is not necessarily true that the eccentricity of every vertex in the new graph is exactly $7$.
In the graph below, the eccentricity of $z$ is $6$. • @monalisa I'll try to think about it, but it seems quite difficult to find a way to make the eccentricity of each vertex exactly $7$. Jun 11, 2018 at 6:03