Dense graph

From Wikipedia, the free encyclopedia

In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges. The opposite, a graph with only a few edges, is a sparse graph.

The distinction between sparse and dense graphs is rather vague. One possibility is to choose a number k with 1 < k < 2 and to define sparse graph to be a graph with |E| = O(|V|k), where |E| denotes the number of edges, |V| the number of vertices, and the letter O refers to the Big O notation (Preiss 1998, p. 534).

For undirected simple graphs, the graph density is defined as:

D = \frac{2|E|}{|V|\,(|V|-1)}

The maximum number of edges is ½ |V| |V−1|, so the maximal density is 1 (for complete graphs) and the minimal density is 0 (Coleman & Moré 1983).

[edit] 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), ... (see, e.g., Diestel, p.189).

[edit] Sparse and tight graphs

Streinu & Theran (2008) 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.

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

[edit] References

  • Paul E. Black, Sparse graph, from Dictionary of Algorithms and Data Structures, Paul E. Black (ed.), NIST. Retrieved on 29 September 2005.
  • 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 .
  • Diestel, Reinhard (2005), Graph Theory, Graduate Texts in Mathematics, Springer-Verlag, ISBN 3540261834 .
  • Preiss, Bruno (1998), Data Structures and Algorithms with Object-Oriented Design Patterns in C++, John Wiley & Sons, ISBN 0-471-24134-2.
  • Streinu, I. & Theran, L. (2008), “Sparse hypergraphs and pebble game algorithms”, European Journal of Combinatorics (special issue for Oriented Matroids '05), arXiv:math/0703921 .
Languages