Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given a simple connected graph $G(V,E)$, is there any relation between the clustering coefficent $C_c = {2|E|\over|V|(|V|-1)}$ of a graph and the length of a all pairs shortest path?

Thank you very much!

share|cite|improve this question
Without further assumptions, only weak relations should exist. In a lollipop graph (take a $n/2$ clique and a disjoint $n/2$ path, and add one more edge from one end of the path to one vertex of the clique), a significant fraction of pairs of vertices are at a distance $\Omega(n)$. This graph has $\Omega(n^2)$ edges. On the other hand, there exist regular expander graphs (with $O(n)$ edges) such that diameter of the graph is as small as $O(\log n)$. – Srivatsan Sep 9 '11 at 15:37
I know what a connected graph is, but what's a simply-connected graph? What is the density of a graph? If a graph is connected and has more than one vertex, then the length of a shortest path is 1 - what do you mean by the length of a shortest path? – Gerry Myerson Sep 10 '11 at 5:36
updated my question! – graphtheory92 Sep 10 '11 at 11:23
What is the clustering coefficient of a graph? What is the meaning of "a all pairs shortest graph"? And why is getting you to write comprehensible questions so often like pulling teeth? – Gerry Myerson Sep 10 '11 at 12:26
updated again. all pairs shortest path is the path from a point to reach all the other points – graphtheory92 Sep 11 '11 at 13:52

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.