1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ For any connected graph G, rad(G) ≤ diam(G) ≤ 2 rad(G). $\endgroup$
    – Aditya
    Jun 19, 2017 at 12:45
  • $\begingroup$ @ADITYA That is a well known result. $\endgroup$
    – monalisa
    Jun 19, 2017 at 12:47
  • 2
    $\begingroup$ Doesn't a star graph allow arbitrarily many vertices for fixed radius and diameter? $\endgroup$
    – hardmath
    Jun 19, 2017 at 12:56
  • $\begingroup$ @hardmath Yeah right. I am trying for a particular case where radius and diameter of a graph are same. Thanks. $\endgroup$
    – monalisa
    Jun 20, 2017 at 4:11
  • 1
    $\begingroup$ 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. $\endgroup$
    – hardmath
    Jun 20, 2017 at 13:19

3 Answers 3

2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

enter image description here

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – hardmath
    Jun 25, 2017 at 15:52

You must log in to answer this question.

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