1
$\begingroup$

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

  • 1
    It 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

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.]