A graph with radius three and diameter four.

Question

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

Answer 1

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

Answer 2

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.