# Number of vertices in a given graph.

Is there any way to find number of vertices in a given graph when radius and diameter of a graph is known? I know the result where we have a found on number of edges i.e.,

$e\leq \frac{n(n-1)}{2}$, where $n$ is the number of vertices in a graph.

Kindly help. Any hint or clue is appreciated. Thanks for the help.

• For any connected graph G, rad(G) ≤ diam(G) ≤ 2 rad(G). Jun 19, 2017 at 12:45
• @ADITYA That is a well known result. Jun 19, 2017 at 12:47
• Doesn't a star graph allow arbitrarily many vertices for fixed radius and diameter? Jun 19, 2017 at 12:56
• @hardmath Yeah right. I am trying for a particular case where radius and diameter of a graph are same. Thanks. Jun 20, 2017 at 4:11
• Perhaps you should add the particular considerations to the Question with an edit. Any hope of getting the bounds you want will rest on those considerations. Jun 20, 2017 at 13:19

There is no hope to upper bound the number of vertices or edges in a graph, given its diameter and radius (that are allowable, of course), as the following construction shows. Let $d$ be the desired diameter and $r$ the radius. We begin with two disjoint paths, $P_r$ and $P_d$, of length $r$ and $d$, respectively. We continue adding leafs to the middle of $P_d$ (creating a star in the middle of the path), which creates arbitrarily many vertices and edges in this graph, but doesn't change the diameter or radius.

We may get a lower bound with another construction. Given that a graph $G$ has radius $r$ and diameter $d$, there exists a path $P_d$ of length $d$ in that graph. Thus, $e(G) \geq d$, $n(G) \geq d+1$. You may do some extra work to incorporate the radius, but be careful as to whether the path $P_r$ that witnesses the radius intersects $P_d$.

Here is a proposition from Diestel's book. I hope it helps.

Thanks for all the provided answers. I just found an article which gives minimum number of vertices in a graph when diameter and radius of graph are known to us. Here is the link to the article. Thanks once again.

http://www.sciencedirect.com/science/article/pii/0012365X73901167

The result is as follows:

Theorem: For all positive integers $m$ and $n$ satisfying $m\leq n\leq 2m-2$ there exist graphs of radius $m$ and diameter $n$. The minimum order of such a graph is $n+m$.

• It is bad form to use mainly a link to Answer the question. At a minimum you should summarize the information to be found at the link, preferably with a quote of the most relevant material. In the alternative you could add the link to your Question. Jun 25, 2017 at 15:52