1
$\begingroup$

Consider an unweighted undirected bi-connected planar graph.

Let $l_{v,u}$ be the length of the shortest path between nodes $v$ and $u$.

Let $l_{max}$ be the length of the longest shortest path from any node to any other node.

The question is:

Are there any known non-trivial upper/lower bounds for $l_{max}$?

It would also help if the bounds are for more general types of graphs.

Another interesting way of looking at the problem is:

  • $l_{max}$ is the maximal number of hops it takes to send a packet in a network from any terminal to any other, when using the shortest possible path.

Please post any link/reference that might be relevant, even if it does not directly solve the problem. Thanks in advance!

Improve this question
$\endgroup$
1
  • 5
    $\begingroup$ Since the graph is biconnected, any two nodes lie on a cycle, and so $\ell_\max \le n/2$. The $n$-cycle is planar and achieves this bound. $\endgroup$
    – Suresh Venkat
    May 12, 2011 at 22:30

1 Answer 1

Reset to default
6
$\begingroup$

$l_{max}$ is called diameter of a graph. I hope this paper will be helpful

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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