3
$\begingroup$

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!

  • 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)$.2011-09-09
  • 0
    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?2011-09-10
  • 0
    updated my question!2011-09-10
  • 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?2011-09-10
  • 0
    updated again. all pairs shortest path is the path from a point to reach all the other points2011-09-11
  • 0
    But the length of a shortest path from a point that visits all the other points will depend on where you start. So I still don't understand the problem. Anyway, the complete graph on $n$ points has the highest clustering coefficient possible, a path graph on $n$ points has the lowest, but in both cases there is a path of length $n-1$ that reaches all the other points. So either there's no relation between the two, or we still have some more teeth to pull.2011-09-11
  • 0
    @Nicola Is my first comment nearly in the right direction? Were you looking for something like that?2011-09-11
  • 0
    yes srivatsan, your is probably very close to the answer. I would like to know, any, if exist possible relation between these two elements2011-09-11

0 Answers 0