# A graph with radius three and diameter four.

I was trying to construct the graphs $$G$$ and $$H$$ by using the cycle graph $$C_9$$ (or $$C_n$$) and $$H$$ and $$G$$ are induced in $$C_n$$.

Graph $$G$$ is formed by attaching a vertex $$x$$ to $$C_9$$ (or $$C_n\geq 7$$) and by making it adjacent to vertex $$1$$ and all the vertices $$j$$, where $$3\leq j\leq 8$$ (or $$3\leq j\leq n-1$$). Here, in $$G$$, vertices $$1$$ and $$x$$ have eccentricity two and rest of the vertices have eccentricity three, shown in the following figure. Similarly, I want to draw a graph $$H$$, where exactly two vertices have eccentricity three and rest of the vertices have eccentricity four.

The graph $$H$$ must be formed by appending exactly one vertex to $$C_n$$.

Kindly help. Any hint will be of great help.

P.S. The construction for graph $$G$$ is for all cycles for $$n\geq9$$.

• I think your construction actually works for $n\ge 7$. Nov 6, 2019 at 10:11
• @Milten yeah right. Nov 6, 2019 at 10:23
• @AngelaRichardson In the present problem, I just need to add one vertex. Not two vertices. Nov 6, 2019 at 11:16
• Do you know if a solution exists? Nov 6, 2019 at 12:38
• In addition to adding a vertex (and edges attached to that vertex), are we allowed to also add extra edges among the original $C_n$ nodes? Nov 6, 2019 at 16:58

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:

1. There are $$5$$ consecutive vertices $$v_1, v_2, v_3, v_4, v_5$$ where $$v_1$$ and $$v_5$$ are adjacent to $$x$$ but $$v_2, v_3, v_4$$ are not. Then $$d(x, v_3) = 3$$.
2. There are $$6$$ consecutive vertices $$v_1, v_2, v_3, v_4, v_5, v_6$$ where $$v_1$$ and $$v_6$$ are adjacent to $$x$$ but $$v_2, v_3, v_4, v_5$$ are not. Then $$d(x, v_3) = d(x, v_4) = 3$$.

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$$.

I believe it is impossible. I'll work by cases of $$S$$ defined to be the longest stretch of consecutive vertices that are not joined to $$x$$.

If $$S\le2$$, then the eccentricity of $$x$$ is $$2$$.

If $$S=3$$, that means that $$x$$ is joined to two vertices of distance $$4$$, say vertices $$1$$ and $$5$$. Then $$x$$, $$1$$ and $$5$$ all have eccentricity $$3$$.

If $$S=4$$, then $$x$$ is joined to two vertices of distance $$5$$, say again vertices $$1$$ and $$5$$ (the other way around the circle), so we have the same problem as in $$S=4$$.

If $$S\ge 5$$, then all vertices on $$C_9$$ have eccentricity $$4$$.

EDIT: I don't have a lot of time right now, so this is just an outline of a proof for $$n\ge10$$.

Define a $$k$$-sequence to be a sequence of $$k$$ consecutive vertices on $$C_n$$ that are not joined to $$x$$.

If $$x$$ has eccentricity $$4$$, then $$S\ge 5$$, but then all vertices have eccentricity $$\ge4$$.

Thus, $$x$$ has eccentricity $$3$$, so $$S\in\{3,4\}$$. If there are two different $$(\ge3)$$-sequences, then some vertices will have eccentricity $$\ge 5$$.

So we must must have one single ($$3$$ or $$4$$)-sequence, and the rest will be $$(\le2)$$-sequences. In this case the two vertices that are connected to $$x$$ on either side of the ($$3$$ or $$4$$)-sequence will have eccentricity $$3$$.

I'll try to get it written properly later, and hopefully make it all a bit clearer.

EDIT: I see Misha Lavrov wrote it very nicely, so I won't update mine. My proof is almost exactly the same as Misha's.

• What for other cycle graphs, $C_n$, $n\geq 10$? Nov 6, 2019 at 13:18
• I appreciate your answer. Thanks for the efforts given by you :) Nov 11, 2019 at 3:45
• @monalisa No problem :) Nov 11, 2019 at 6:48