Dense graph

Dense graph

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, and depends on the context.

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

Contents

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

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.

Sparse and dense classes of graphs

Ossona de Mendez & Nešetřil (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 has 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 opposite, if such a threshold does not exist, the class is nowhere dense.

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, doi:10.1137/0720013 .
  • Diestel, Reinhard (2005), Graph Theory, Graduate Texts in Mathematics, Springer-Verlag, ISBN 3540261834, OCLC 181535575 .
  • Preiss, Bruno (1998), Data Structures and Algorithms with Object-Oriented Design Patterns in C++, John Wiley & Sons, ISBN 0-471-24134-2 .
  • Ossona de Mendez, Patrice; Nešetřil, Jaroslav (2010). "From Sparse Graphs to Nowhere Dense Structures: Decompositions, Independence, Dualities and Limits". European Congress of Mathematics. European Mathematical Society. pp. 135–165. 
  • 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 .

Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • dense — [ dɑ̃s ] adj. • fin XIVe; lat. densus « épais » 1 ♦ Qui est compact, épais. Brouillard dense. ⇒ impénétrable. Le feuillage dense des arbres. ⇒ abondant, serré, touffu. ♢ Une foule dense, nombreuse et rassemblée. Circulation très dense. 2 ♦… …   Encyclopédie Universelle

  • Dense subgraph — An example of a graph G with density dG = 1.375 and it s densest subgraph induced by the vertices b,c,d and h in red with density 1.4 In computer science the notion of highly connect …   Wikipedia

  • List of graph theory topics — This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 …   Wikipedia

  • Clique (graph theory) — A graph with 23 1 vertex cliques (its vertices), 42 2 vertex cliques (its edges), 19 3 vertex cliques (the light blue triangles), and 2 4 vertex cliques (dark blue). Six of the edges and 11 of the triangles form maximal cliques. The two dark blue …   Wikipedia

  • Claw-free graph — A claw In graph theory, an area of mathematics, a claw free graph is a graph that does not have a claw as an induced subgraph. A claw is another name for the complete bipartite graph K1,3 (that is, a star graph with three edges, three leaves, and …   Wikipedia

  • Scene graph — A scene graph is a general data structure commonly used by vector based graphics editing applications and modern computer games. Examples of such programs include AutoCAD, Adobe Illustrator, Acrobat 3D, OpenSceneGraph and CorelDRAW.The scene… …   Wikipedia

  • Neighbourhood (graph theory) — A graph consisting of 6 vertices and 7 edges For other meanings of neighbourhoods in mathematics, see Neighbourhood (mathematics). For non mathematical neighbourhoods, see Neighbourhood (disambiguation). In graph theory, an adjacent vertex of a… …   Wikipedia

  • Quantum graph — In mathematics and physics, a quantum graph is a linear, network shaped structure whose time evolution is described by a system of schrödinger equations or, more generally, by a set of evolution equations associated with differential or pseudo… …   Wikipedia

  • Triangle-free graph — In the mathematical area of graph theory, a triangle free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4,… …   Wikipedia

  • Matching (graph theory) — In the mathematical discipline of graph theory, a matching or independent edge set in a graph is a set of edges without common vertices. It may also be an entire graph consisting of edges without common vertices. Covering packing dualities… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”