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.

Does the shortest path increase or decrease with graph density in undirected graphs? Or is there no clear relationship?

share|improve this question
1  
It is known that there is no upper bound for the chromatic number of a graph using graph density alone (see this paper). Also, there is a classical result of Erdos that says that for $k\ge2$ there exist graphs with chromatic number and girth $>k$, so I would expect the answer to be that there is no clear relationship - but I am unsure. HTH. –  sai May 18 '12 at 2:48

1 Answer 1

Here's an "experimental mathematics" answer.

The following plot shows the average path length vs. graph density in Erdős–Rényi random graphs $G(50,p)$: 10 samples for each probability $p \in \{0.01,0.02,\ldots,1\}$.

average path length vs. graph density in Erdős–Rényi random graphs

Generally, we can see that graphs with higher density have shorter average path length (which is intuitive).

Note: Some of the graphs with close-to-$0$ densities have a small "average path length", but this is an anomaly of the definition (if there's no path, they have path length $0$).

Comments:

  • It is likely that under different random graph models the behaviour is different (as, perhaps, it might be for, say, real-world networks).
  • There are probably going to be contrived examples far away from the main curve, but the experimental results above suggest they will be relatively rare.

[The above figure was computed in R using the igraph extension. The relevant functions are average.path.length and graph.density. I also plotted the results using tikzDevice, making some manual edits.]

share|improve this answer

Your Answer

 
discard

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

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