combinatoricsdiscrete mathematicsgraph theory
I was trying to convert graphs $C_8$ and $C_9$ into graphs $A$ and $B$, by adding two extra vertices, such that both $A$ and $B$ contains exactly two vertices with eccentricity three and rest with eccentricity four, and $C_8$ is induced in $A$ and $C_9$ is induced in $B$. Kindly help me to get the graph (may be by adding 3 vertices). Any hint or suggestion will be helpful. Following is my (failed) attempt.
Graph $A$
Graph $B$
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.
It's impossible for larger cycles ($n\ge 10$) as well.
Suppose that the center vertex $x$ has eccentricity $4$. Then there is a vertex $v$ at distance $4$ from $x$. Let $w$ be the vertex opposite from $v$ along the cycle (or one such vertex, when $n$ is odd). Then $d(v,w) > 4$: $v$ cannot reach $w$ in $4$ or fewer steps by going along the cycle (it is too far), but $v$ cannot reach $w$ in $4$ or fewer steps by going through $x$ (it takes $4$ steps just to get to $x$).
Therefore $x$ has eccentricity $3$. There must be a vertex at distance $3$ from $x$, and this can happen in two ways:
In case 1, in order for $v_3$ to have eccentricity at most $4$, every vertex which is $5$ or more steps from $v_3$ along the cycle must be adjacent to $x$. (That way, there is a length-$4$ path from $v_3$ to such a vertex by going through $x$.) We get a graph that contains at least the following edges:
(There don't need to be exactly three vertices opposite $v_3$ which we join to $x$, but there is at least one.)
But now, both $v_1$ and $v_5$ can already reach every other vertex in at most $3$ steps, and that (together with $x$) is too many vertices of eccentricity $3$.
A similar thing happens in case 2: we have to join $x$ to every vertex that's 5 or more steps away from either $v_3$ and $v_4$, and then $v_1$ and $v_6$ have eccentricity $3$ as well as $x$.
Best Answer
I was able to mess around with this and get an answer, but I wasn't able to find a great procedure. I really just arrived at the conclusion that the vertices with eccentricity $3$ probably should be the newly introduced vertices. In order for this to work out any "bridge" that they create in the original $C_8$ (or $C_9$) couldn't be a "shortcut" for any vertices in the cycle. Note how both graphs are structurally similar. I bet this concept could generalize nicely for higher order cycles with a little bit of work.
Here is your graph $A$ starting from a $C_8$. The two bottom vertices colored in green are the ones with eccentricity $3$. The red ones have eccentricity $4$.
Here is your graph $B$ starting from a $C_9$. Colored similarly as above.