5
$\begingroup$

I am given a graph $G$ with diameter two. I have to prove that I have to add minimum $2r-3$ vertices to $G$ to form a graph $H$ such that $H$ contains exactly two vertices with eccentricity $r+1$ (obviously peripheral vertices) and rest with eccentricity $r$ (central vertices), where $r\geq 4$. Also, $G$ is induced in $H$.

I am stuck at a particular part of the proof. Since diameter of $G$ is two, $G$ can at the most contain one diametral vertex or at the most one vertex with eccentricity $r+1$. I divided the proof in two cases. In first part, $G$ contains a vertex with eccentricity $r+1$. This part has been proved by me. In second case, $G$ does not contain a vertex with eccentricity $r+1$ and I am stuck in this case. However, I tried to prove it, but I am feeling that it is not surely true.

In the following attempt I consider a $z-w$ walk of length $r$ but I feel it is wrong as we already get a $z-w$ path of length $r$ lying on $x-y$ path since $z$ is adjacent to $x$.

MY ATTEMPT:

Let $P$ be a diametral path in $H$ of length $r+1$ with end vertices $x$ and $y$ ($x,y\notin G$).

Since $diam(G) =2$, at the most 3 vertices of $G$ can lie on $P$ and thus

$P$ contains at least $r-1$ new vertices. Since $r\geq 4$, $r+1\geq 5$ and $P$ contains at least six vertices. If $x$ and $y$ are end vertices of $P$ which are not in $G$ then there exists $z\notin V(G)$ and $x\sim z$ or $y\sim z$. Without loss of generality, let $x\sim z$. Since $e(z)=r$, there exists a $z-w$ path $P_2$ such that $l(P_2)=r =d(z,w)$. Now, the path $P$ can not be extended, otherwise $d(x,y)>r+1$, and $P_2$ contains at most three vertices from $G$. This follows that at least $r-2$ vertices in $P_2$ are not in $G$. This proves that we need to add at least $(r-1) +(r-2) = 2r-3$ new vertices.

Is this proof correct? I feel this proof is still incomplete. Somewhere I feel that I am missing some part. Kindly help me. Thanks a lot for your time and help.

P.S. It might be possible that $P$ and $P_2$ intersect at many vertices. In that case how to prove the result.

----------------------------------------------------

Added one more point in the proof (edited proof)

$G$ does not contain any diametral vertex.

Since $diam(G) =2$, here also $P$ contains at least $r-1$ new vertices. Since $r\geq 4$ and $r+1\geq 5$, $P$ contains at least six vertices. If $x$ and $y$ are end vertices of $P$ which are not in $G$ then there exists $z\notin V(G)$ and $x\sim z$ or $y\sim z$. Without loss of generality, let $x\sim z$. Since $e(z)=r$, there exists a $z$--$w$ path $P_2: z,w_1,w_2,\ldots,w_r=w$ such that $l(P_2)=r =d(z,w)$. Now, the path $P$ can not be extended, otherwise $d(x,y)>r+1$. Now, the $P_2$ contains at most three vertices from $G$ since $diam(G) =2$. Further, if $P_2$ intersect vertices of the $P$ then $d(z,w)<r$, which is a contradiction because $e(z) = r$. This follows that at least $r-2$ vertices in $P_2$ are not in $G$.

$\endgroup$
1
  • 2
    $\begingroup$ The question might get more attention if you rewrite the title to be more informative of what it is about. $\endgroup$ Commented Jun 24, 2019 at 13:07

1 Answer 1

1
$\begingroup$

Let $v$ be a vertex of $G$ with at least one neighbor among the new vertices. For $i \in \{1,\ldots,r\}$, let $S_i$ be the set of vertices at distance exactly $i$ from $v$. Note that $S_1$ and $S_2$ have at least one new vertex each. Suppose we show that all but one $S_i$ for $i \geq 3$ have at least two vertices. Then the number of new vertices is at least $2(n-3)+1+2=2n-3$. Let $S_i=\{x\}$ for some $i$. Then $x$ is a cut-vertex and it must be the case that its eccentricity is $r$, say component $C$ of $H \setminus v$ has $y$ such that $d(x,y)=r$, and $V(H) \setminus (C \cup \{v\})$ consists of one vertex of eccentricity $r+1$ which is a neighbor of $x$. This shows that there can be at most two cut-vertices in $H$, but hopefully this idea is sufficient to complete the proof with a more careful analysis.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .