To construct a graph using path graph $P_4$

Question

I was trying to construct a graph $G_1$ and $G_2$, wherein both graphs $P_4$ is an induced graph. Graph $G_1$ is such that it contains exactly one vertex of eccentricity two and rest of the vertices with eccentricity three. Similarly, the graph $G_2$ is such that it contains exactly one vertex of eccentricity three and the rest of the vertices with eccentricity four. In both the cases, $P_4$ is induced in $G_1$ and $G_2$.

I tried in the following manner.

For $G_1$, I added $6$ vertices to $P_4$ and got the result, and for $G_2$, I added $10$ vertices to $P_4$ and got the result. However, later I got that $G_1$ can be obtained with the fewer number of vertices. Can $G_2$ be also obtained by adding less than $10$ vertices, if possible? Kindly help me to get the graph. Any hint or suggestion is helpful.

My attempt : (numbers are the eccentricity of the vertices)

Graph $G_1$ with less number of vertices:

P.S.

For $G_2$, I also got an example. consider $C_6$ with vertices $1,2,3,4,5,6$. Add $5$ vertices $1′,2′,3′,4′,5′$ and make edges $1′2′,2′3′,3′4′,4′5′$, and $xx′$, where $x=1,2,3,4,5$. This also gives a graph with exactly one vertex with eccentricity $3$ and rest with $4$. The total number of vertices is $11$. Can we think of a smaller order? I am wondering that.

Answer 1

HINT only (for now).

Your $G_2$ has $14$ nodes. I found one with only $11$ nodes. You said "Any hint or suggestion is helpful" so perhaps you prefer just hints so that you can enjoy finding it yourself? :) Anyway if these hints are not enough feel free to ask again.

Inspired by the smaller $G_1$ solution...

• Lets start with an outer ring. To achieve a "base" eccentricity of $4$, the ring has $8$ nodes, i.e. opposite nodes have distance $4$. (Analogous to the smaller $G_1$ having an outer ring of $6$ nodes to achieve a "base" eccentricity of $3$.)

• Lets add a center node $C$, and lets "attach" $C$ to the ring at $3$ nodes $X,Y,Z$. We eventually want $C$ to have the lower eccentricity $3$, so intuitively you want to "space out" $X,Y,Z$ around the ring.

• If we "attach" using edges $(C,X), (C,Y), (C,Z)$ then $C$ will have eccentricity $2$. So some of the attachments must be multi-hop path(s), e.g. $(C,A), (A,X)$ would make a $2$-hop path from $C$ to $X$. This of course adds an "extra" internal node $A$.

• [Hand crafting time] Can you find a way to use as few of these "extra" nodes as possible? I found a way to use only $2$ of them, for a total of $8 + 1 + 2 = 11$ nodes, while maintaining $C$'s eccentricity at $3$ and everyone else's at $4$.

No idea if $11$ is the fewest nodes possible.

Incidentally, note that $P_4$ being induced was not part of the consideration. In a sense having an induced $P_4$ is "easy" to satisfy, so I worried about the eccentricity constraints first and the final graph does have an induced $P_4$ (many, many such subgraphs).

UPDATE

Here is my $11$-node solution. The outer square is the ring of $8$ nodes and the center node has eccentricity $3$. My labeling also shows this is the same as the OP's example minus two edges ($22'$ and $44'$).

6-----1-----1'
|     |     |
|     2     |
|     |     |
5--4--3     2'
|      \    |
|       \   |
|        \  |
|         \ |
|          \|
5'----4'----3'