A trivalent graph with $2k$ nodes has maximum diameter $2k-1$, where the diameter is defined by the maximum distance between two nodes. So, my question is the following:
What is the lower bound on the diameter of a trivalent graph with $2k$ nodes?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
If diameter equals $d$, the total number $n$ of vertices does not exceed $1+3+3\cdot 2+\dots+3\cdot 2^{d-1}=3\cdot 2^d-2$, this gives you a lower estimate on $d$ which is less or more sharp.
answered Jun 24, 2017 at 7:03
-
$\begingroup$ Thank you very much for your answer. This is the maximum number of nodes in a ball of radius $d$ . $\endgroup$ Commented Jun 24, 2017 at 7:14
-
1$\begingroup$ Yes, it is. Sometimes it is sharp, for example, $d=2$, $n=2k=10$, Petersen's graph. $\endgroup$ Commented Jun 24, 2017 at 7:56
$\begingroup$
$\endgroup$
0
To amplify on Fedor's answer, random graphs come close to this bound, for a lot more color see the ancient (but still useful) 1987 paper by Fan Chung.
answered Jun 24, 2017 at 13:12