Dense graph

Template:Short description Template:CS1 config In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges (where every pair of vertices is connected by one edge). The opposite, a graph with only a few edges, is a sparse graph. The distinction of what constitutes a dense or sparse graph is ill-defined, and is often represented by 'roughly equal to' statements. Due to this, the way that density is defined often depends on the context of the problem.

The graph density of simple graphs is defined to be the ratio of the number of edges Template:Math with respect to the maximum possible edges.

For undirected simple graphs, the graph density is:

$D=\frac{|E|}{(\genfrac{}{}{0ex}{}{|V|}{2})}=\frac{2|E|}{|V|(|V|-1)}$

For directed, simple graphs, the maximum possible edges is twice that of undirected graphs (as there are two directions to an edge) so the density is:

$D=\frac{|E|}{2(\genfrac{}{}{0ex}{}{|V|}{2})}=\frac{|E|}{|V|(|V|-1)}$

where Template:Mvar is the number of edges and Template:Mvar is the number of vertices in the graph. The maximum number of edges for an undirected graph is $(\genfrac{}{}{0ex}{}{|V|}{2})=\frac{|V|(|V|-1)}{2}$, so the maximal density is 1 (for complete graphs) and the minimal density is 0.Template:Sfn

For families of graphs of increasing size, one often calls them sparse if $D\to 0$ as $|V|\to \mathrm{\infty }$. Sometimes, in computer science, a more restrictive definition of sparse is used like $|E|=O(|V|\log |V|)$ or even $|E|=O(|V|)$.

Upper density

Upper density is an extension of the concept of graph density defined above from finite graphs to infinite graphs. Intuitively, an infinite graph has arbitrarily large finite subgraphs with any density less than its upper density, and does not have arbitrarily large finite subgraphs with density greater than its upper density. Formally, the upper density of a graph Template:Mvar is the infimum of the values α such that the finite subgraphs of Template:Mvar with density α have a bounded number of vertices. It can be shown using the Erdős–Stone theorem that the upper density can only be 1 or one of the superparticular ratios Template:Math

Sparse and tight graphs

Template:Harvtxt and Template:Harvtxt define a graph as being Template:Math-sparse if every nonempty subgraph with Template:Mvar vertices has at most Template:Math edges, and Template:Math-tight if it is Template:Math-sparse and has exactly Template:Math edges. Thus trees are exactly the Template:Math-tight graphs, forests are exactly the Template:Math-sparse graphs, and graphs with arboricity Template:Mvar are exactly the Template:Math-sparse graphs. Pseudoforests are exactly the Template:Math-sparse graphs, and the Laman graphs arising in rigidity theory are exactly the Template:Math-tight graphs.

Other graph families not characterized by their sparsity can also be described in this way. For instance the facts that any planar graph with Template:Mvar vertices has at most Template:Math edges (except for graphs with fewer than 3 vertices), and that any subgraph of a planar graph is planar, together imply that the planar graphs are Template:Math-sparse. However, not every Template:Math-sparse graph is planar. Similarly, outerplanar graphs are Template:Math-sparse and planar bipartite graphs are Template:Math-sparse.

Streinu and Theran show that testing Template:Math-sparsity may be performed in polynomial time when Template:Mvar and Template:Mvar are integers and Template:Math.Template:Sfn

For a graph family, the existence of Template:Mvar and Template:Mvar such that the graphs in the family are all Template:Math-sparse is equivalent to the graphs in the family having bounded degeneracy or having bounded arboricity. More precisely, it follows from a result of Template:Harvtxt that the graphs of arboricity at most Template:Mvar are exactly the Template:Math-sparse graphs.Template:Sfn Similarly, the graphs of degeneracy at most Template:Mvar are $(d,(\genfrac{}{}{0ex}{}{d+1}{2}))$-sparse graphs.Template:Sfn

Sparse and dense classes of graphs

Template:Harvtxt considered that the sparsity/density dichotomy makes it necessary to consider infinite graph classes instead of single graph instances. They defined somewhere dense graph classes as those classes of graphs for which there exists a threshold t such that every complete graph appears as a t-subdivision in a subgraph of a graph in the class. To the contrary, if such a threshold does not exist, the class is nowhere dense.

The classes of graphs with bounded degeneracy and of nowhere dense graphs are both included in the biclique-free graphs, graph families that exclude some complete bipartite graph as a subgraph.Template:Sfn

See also

• Bounded expansion
• Dense subgraph

References

• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation

Further reading

• Template:Citation