Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
2  
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
1  
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

 
discard

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

Browse other questions tagged or ask your own question.