Menu
Home Explore People Places Arts History Plants & Animals Science Life & Culture Technology
On this page
Dense graph
Graph in which the number of edges is close to the maximum for its number of vertices

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 |E| with respect to the maximum possible edges.

For undirected simple graphs, the graph density is:

D = | E | ( | V | 2 ) = 2 | E | | V | ( | V | − 1 ) {\displaystyle D={\frac {|E|}{\binom {|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 = | E | 2 ( | V | 2 ) = | E | | V | ( | V | − 1 ) {\displaystyle D={\frac {|E|}{2{\binom {|V|}{2}}}}={\frac {|E|}{|V|(|V|-1)}}}

where E is the number of edges and V is the number of vertices in the graph. The maximum number of edges for an undirected graph is ( | V | 2 ) = | V | ( | V | − 1 ) 2 {\displaystyle {\binom {|V|}{2}}={\frac {|V|(|V|-1)}{2}}} , so the maximal density is 1 (for complete graphs) and the minimal density is 0.

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

We don't have any images related to Dense graph yet.
We don't have any YouTube videos related to Dense graph yet.
We don't have any PDF documents related to Dense graph yet.
We don't have any Books related to Dense graph yet.
We don't have any archived web articles related to Dense graph yet.

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 G is the infimum of the values α such that the finite subgraphs of G 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 0, ⁠1/2⁠, ⁠2/3⁠, ⁠3/4⁠, ⁠4/5⁠, … ⁠n/n + 1⁠2

Sparse and tight graphs

Lee & Streinu (2008) and Streinu & Theran (2009) define a graph as being (k, l)-sparse if every nonempty subgraph with n vertices has at most kn − l edges, and (k, l)-tight if it is (k, l)-sparse and has exactly kn − l edges. Thus trees are exactly the (1,1)-tight graphs, forests are exactly the (1,1)-sparse graphs, and graphs with arboricity k are exactly the (k,k)-sparse graphs. Pseudoforests are exactly the (1,0)-sparse graphs, and the Laman graphs arising in rigidity theory are exactly the (2,3)-tight graphs.3

Other graph families not characterized by their sparsity can also be described in this way. For instance the facts that any planar graph with n vertices has at most 3n – 6 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 (3,6)-sparse. However, not every (3,6)-sparse graph is planar. Similarly, outerplanar graphs are (2,3)-sparse and planar bipartite graphs are (2,4)-sparse.

Streinu and Theran show that testing (k,l)-sparsity may be performed in polynomial time when k and l are integers and 0 ≤ l < 2k.4

For a graph family, the existence of k and l such that the graphs in the family are all (k,l)-sparse is equivalent to the graphs in the family having bounded degeneracy or having bounded arboricity. More precisely, it follows from a result of Nash-Williams (1964) that the graphs of arboricity at most a are exactly the (a,a)-sparse graphs.5 Similarly, the graphs of degeneracy at most d are ( d , ( d + 1 2 ) ) {\displaystyle \left(d,{\binom {d+1}{2}}\right)} -sparse graphs.6

Sparse and dense classes of graphs

Nešetřil & Ossona de Mendez (2010) 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.7

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

See also

Notes

Further reading

References

  1. Coleman & Moré 1983. - Coleman, Thomas F.; Moré, Jorge J. (1983), "Estimation of sparse Jacobian matrices and graph coloring Problems", SIAM Journal on Numerical Analysis, 20 (1): 187–209, doi:10.1137/0720013 https://doi.org/10.1137%2F0720013 ↩

  2. See, e.g., Diestel 2005, 5th edition, p. 189. - Diestel, Reinhard (2005), Graph Theory, Graduate Texts in Mathematics, Springer-Verlag, ISBN 3-540-26183-4, OCLC 181535575 https://search.worldcat.org/oclc/181535575 ↩

  3. Lee & Streinu 2008 and Streinu & Theran 2009 - Lee, Audrey; Streinu, Ileana (2008), "Pebble game algorithms and sparse graphs", Discrete Mathematics, 308 (8): 1425–1437, arXiv:math/0702129, doi:10.1016/j.disc.2007.07.104, MR 2392060 https://arxiv.org/abs/math/0702129 ↩

  4. Streinu & Theran 2009. - Streinu, I.; Theran, L. (2009), "Sparse hypergraphs and pebble game algorithms", European Journal of Combinatorics, 30 (8): 1944–1964, arXiv:math/0703921, doi:10.1016/j.ejc.2008.12.018 https://arxiv.org/abs/math/0703921 ↩

  5. Nash-Williams 1964. - Nash-Williams, C. St. J. A. (1964), "Decomposition of finite graphs into forests", Journal of the London Mathematical Society, 39 (1): 12, doi:10.1112/jlms/s1-39.1.12, MR 0161333 https://doi.org/10.1112%2Fjlms%2Fs1-39.1.12 ↩

  6. Lick & White 1970. - Lick, Don R; White, Arthur T (1970), "k-Degenerate graphs", Canadian Journal of Mathematics, 22 (5): 1082–1096 https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/kdegenerate-graphs/45829E7755FA1F4D72FD84530F492E8A ↩

  7. Nešetřil & Ossona de Mendez 2010. Properties of the nowhere dense vs somewhere dense dichotomy are discussed by Nešetřil & Ossona de Mendez 2012. - Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2010), "From Sparse Graphs to Nowhere Dense Structures: Decompositions, Independence, Dualities and Limits", European Congress of Mathematics, European Mathematical Society, pp. 135–165 ↩

  8. Telle & Villanger 2012. - Telle, Jan Arne; Villanger, Yngve (2012), "FPT algorithms for domination in biclique-free graphs", in Epstein, Leah; Ferragina, Paolo (eds.), Algorithms – ESA 2012: 20th Annual European Symposium, Ljubljana, Slovenia, September 10–12, 2012, Proceedings, Lecture Notes in Computer Science, vol. 7501, Springer, pp. 802–812, doi:10.1007/978-3-642-33090-2_69 https://doi.org/10.1007%2F978-3-642-33090-2_69 ↩