# Increasing (or changing) the eccentricity of a vertex in a given graph.

I considered a graph, path $$P_8$$ and added two more vertices such that eccentricity of two vertices is three and rest of the vertices have eccentricity four, and $$P_8$$ is induced in the new graph. I got the following figure, where exactly two vertices (numbered 2 and 7) are central vertices (eccentricity two) and rest are non-central vertices i.e., diametral vertices (eccentricity four) and $$P_8$$ is induced in this graph.

Is there any way to get the same result for the graph path $$P_9$$, or other path graphs, by adding exactly two vertices. Any kind of help or suggestion will be highly useful for me. I am thankful in advance for the help.

• What exactly is the result that you are looking for? Are you looking to add two vertices to $P_9$ to achieve diameter $4$ and radius $3$? Nov 6, 2018 at 6:40
• Yeah, You are right, but the condition is that only two vertices should have eccentricity 3 and rest should have eccentricity four. Nov 6, 2018 at 7:18

I want to note that there is one other graph (and only one up to isomorphism) that meets your conditions on $$P_8$$:

Here, vertices $$7$$ and $$9$$ have eccentricity $$3$$ and the rest have eccentricity $$4$$.

I have found $$76$$ such graphs on $$P_9$$ though many of these are not unique up to isomorphism. Also, some of the graphs are subgraphs of other such graphs. A couple are listed below.

Above, vertices $$1$$ and $$2$$ have eccentricity $$3$$ and the rest have eccentricity $$4$$.

Above, vertices $$7$$ and $$10$$ have eccentricity $$3$$ and the rest have eccentricity $$4$$.

I would be happy to provide more information about the graphs if you want more. Just comment.

• Amazing. That is really helpful to me. I am glad that you helped me. Really thanks a lot. Nov 8, 2018 at 8:30
• How did you manage to get such a large family of graphs? Nov 8, 2018 at 11:04
• @monalisa I used SageMath to look for graphs that had the required property. My code produced $14$ such non-isomorphic graphs on $P_9$ and $2$ on $P_8$. I would be happy to post a second answer here to classify the $14$ graphs. Just let me know. Nov 8, 2018 at 21:16
• That would be so helpful to me if you can share them. Once again thanks a lot for your efforts. Nov 11, 2018 at 8:54
These are the $$15$$ graphs (up to isomorphism) with this property on $$P_9$$.