0
$\begingroup$

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?

$\endgroup$

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you very much for your answer. This is the maximum number of nodes in a ball of radius $d$ . $\endgroup$ 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$ Jun 24, 2017 at 7:56
1
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.