Does the shortest path increase or decrease with graph density in undirected graphs? Or is there no clear relationship?
What is the relationship between shortest path and density for undirected graph?
1
$\begingroup$
graph-theory
-
1It is known that there is no upper bound for the chromatic number of a graph using graph density _alone_ (see [this paper](http://www.sciencedirect.com/science/article/pii/0095895677900375)). 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. – 2012-05-18
1 Answers
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\}$.
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.]