To construct a graph using path graph $P_4$

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.

• Where does this problem come from, and why the constraint that $P_4$ must be an induced graph? It seems to me that the eccentricity constraints are much tougher (and would already make a great puzzle without adding the $P_4$ requirement). Mar 29, 2019 at 19:11
• @antkam An assignment problem by the professor. Mar 29, 2019 at 19:32

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'

• 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$. Number of vertices is $11$. Can we think of smaller order? I am wondering that. Mar 29, 2019 at 4:50
• @monalisa - very interesting! that is dramatically different from my example, and still the same no. of nodes $11$... Mar 29, 2019 at 12:40
• yeah :) Just trying for a fewer number of nodes, if possible. Mar 29, 2019 at 12:41
• in your example, you only need edges $xx'$ for $x = 1, 3, 5$. this of course doesn't change the number of nodes. also i found another neat solution, but with $15$ nodes: the $4$-dimensional hypercube with any one vertex deleted. Apr 2, 2019 at 18:17
• no, thank YOU for the problem! :) i found it a lot of fun and it's something i can think about in my spare time. BTW i just realized that your example, when modified to have edges $xx'$ only for $x=1,3,5$, is actually the same as my example. Apr 3, 2019 at 22:01