Does the shortest path increase or decrease with graph density in undirected graphs? Or is there no clear relationship?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Here's an "experimental mathematics" answer.
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$).
[The above figure was computed in R using the igraph extension. The relevant functions are