1
$\begingroup$

Characteristic (average) path length is defined here: https://cs.stackexchange.com/a/7538/20256

I want to establish upper and lower bounds on the CPL for a graph of $n$ vertices, and any positive number of edges, such that each vertex has a degree of at least 1 (i.e. the graph is connected). Assume that the graph is undirected, and unweighted.

My initial guess on the upper bound was a "straight line" of vertices, i.e.:

1 -- 2 -- ... -- n-1 -- n

with edges denoted as "--".

Working through the calculations, I arrived at the value for the CPL of this graph to be $\frac{n+1}{3}$. However, I cannot come to a proof on this being the absolute upper bound.

Also, what would a lower bound be? I conjecture that a regular graph (http://en.wikipedia.org/wiki/Regular_graph) would be the correct answer, but haven't found a proof for this either.

Edit: the lower bound is 1. The reason is construct a fully connected graph (i.e. any vertex is connected to all other vertices by 1 edge).

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.