# Construction of a graph with specific properties (of specific eccentricities)

In the following figure I tried to draw a graph from $P_{11}$ (vertex set as $u_1,\ldots,u_{11}$) by adding two vertices(red colored) to $P_{11}$, with exactly two vertices having eccentricity five and rest of the vertices having eccentricity four. I want the resultant graph to an induced subgraph of $P_{11}$.

I almost succeeded but unable to move forward from here. I want eccentricity of $u_1$ and $y$ to be fourKindly help. Thanks a lot for the help.

Note: Eccentricity of vertices is given in numbers.

Is there any other way to make $P_{11}$ as induced subgraph of a graph $G$, Eccentricity of every vertex is four and two vertices have acc 5. $G$ is obtained by adding two vertices to $P_{11}$.

• You could surely write some code that checks the eccentricity of each vertex in every possible graph formed by adding two vertices to $P_11$ (there are approximately $2^{\binom{13}{2}-10}$ such graphs)? Jan 8, 2018 at 13:46
• Could you clarify what you mean by "I want the resultant graph to [be?] an induced subgraph of $P_{11}$?" Jan 8, 2018 at 18:14
• @FabioSomenzi ... My original graph is $P_{11}$ and I added two new vertices, red in color. Now I want $P_{11}$ to be an induced subgraph of this final graph (where I added two vertices). Jan 9, 2018 at 3:13

Since the original question does not contain the definition of eccentricity, recall that the eccentricity of a vertex $v$ in a graph $G$ is the maximum distance between $v$ and any other vertex $u$ of $G$.
The following graph has two vertices with eccentricity 5 (green vertices $u_1$ and $u_{11}$) and the remaining vertices have eccentricity 4. It is constructed by adding two red vertices $u_{12}$ and $u_{13}$ to a path of length 11. Deleting $u_{12}$ and $u_{13}$ recovers the path of length 11, and thus the path of length 11 is an induced subgraph. Each vertex is labeled with its name $u_i$ and its eccentricity.