Editing Glossary of graph theory (section)

==D==
{{glossary}}

{{term|DAG}}
{{defn|Abbreviation for [[directed acyclic graph]], a directed graph without any directed cycles.}}

{{term|deck}}
{{defn|The multiset of graphs formed from a single graph {{mvar|G}} by deleting a single vertex in all possible ways, especially in the context of the [[reconstruction conjecture]]. An edge-deck is formed in the same way by deleting a single edge in all possible ways. The graphs in a deck are also called ''cards''. See also {{gli|critical}} (graphs that have a property that is not held by any card) and {{gli|hypo-}} (graphs that do not have a property that is held by all cards).}}

{{term|decomposition}}
{{defn|See {{gli|tree decomposition}}, {{gli|path decomposition}}, or {{gli|branch-decomposition}}.}}

{{term|degenerate}}
{{term|degeneracy|multi=y}}
{{defn|A {{mvar|k}}-degenerate graph is an undirected graph in which every induced subgraph has minimum degree at most {{mvar|k}}. The [[Degeneracy (graph theory)|degeneracy]] of a graph is the smallest {{mvar|k}} for which it is {{mvar|k}}-degenerate. A degeneracy ordering is an ordering of the vertices such that each vertex has minimum degree in the induced subgraph of it and all later vertices; in a degeneracy ordering of a {{mvar|k}}-degenerate graph, every vertex has at most {{mvar|k}} later neighbours. Degeneracy is also known as the {{mvar|k}}-core number, width, and linkage, and one plus the degeneracy is also called the coloring number or Szekeres–Wilf number. {{mvar|k}}-degenerate graphs have also been called {{mvar|k}}-inductive graphs.}}

{{term|degree}}
{{defn|no=1|The [[degree (graph theory)|degree]] of a vertex in a graph is its number of incident edges.<ref name="clrs"/> The degree of a graph {{mvar|G}} (or its maximum degree) is the maximum of the degrees of its vertices, often denoted {{math|&Delta;(''G'')}}; the minimum degree of {{mvar|G}} is the minimum of its vertex degrees, often denoted {{math|''&delta;''(''G'')}}. Degree is sometimes called ''valency''; the degree of {{mvar|v}} in {{mvar|G}} may be denoted {{math|''d''<sub>''G''</sub>(''v'')}}, {{math|''d''(''G'')}}, or {{math|deg(''v'')}}. The total degree is the sum of the degrees of all vertices; by the [[handshaking lemma]] it is an even number. The [[degree sequence]] is the collection of degrees of all vertices, in sorted order from largest to smallest. In a directed graph, one may distinguish the in-degree (number of incoming edges) and out-degree (number of outgoing edges).<ref name="clrs"/>}}
{{defn|no=2|The homomorphism degree of a graph is a synonym for its ''Hadwiger number'', the order of the largest clique minor.}}

{{term|delta|&Delta;, ''&delta;''}}
{{defn|{{math|&Delta;(''G'')}} (using the Greek letter delta) is the maximum degree of a vertex in {{mvar|G}}, and {{math|''&delta;''(''G'')}} is the minimum degree; see {{gli|degree}}.}}

{{term|density}}
{{defn|In a graph of ''n'' nodes, the density is the ratio of the number of edges of the graph to the number of edges in a complete graph on ''n'' nodes. See [[dense graph]].}}

{{term|depth}}
{{defn|The depth of a node in a rooted tree is the number of edges in the path from the root to the node. For instance, the depth of the root is 0 and the depth of any one of its adjacent nodes is 1. It is the level of a node minus one. Note, however, that some authors instead use ''depth'' as a synonym for the ''level'' of a node.<ref>{{citation|url=https://xlinux.nist.gov/dads/HTML/depth.html|title=depth|publisher = [[NIST]]}}</ref>}}

{{term|diameter}}
{{defn|The [[diameter (graph theory)|diameter]] of a connected graph is the maximum length of a [[shortest path]]. That is, it is the maximum of the distances between pairs of vertices in the graph. If the graph has weights on its edges, then its weighted diameter measures path length by the sum of the edge weights along a path, while the unweighted diameter measures path length by the number of edges.
For disconnected graphs, definitions vary: the diameter may be defined as infinite, or as the largest diameter of a connected component, or it may be undefined.}}

{{term|diamond}}
{{defn|The [[diamond graph]] is an undirected graph with four vertices and five edges.}}

{{term|diconnected}}
{{defn|{{gli|Strong}}ly {{gli|connected}}. (Not to be confused with {{gli|disconnected}})}}

{{term|digon}}
{{defn|A [[digon]] is a simple cycle of length two in a directed graph or a multigraph. Digons cannot occur in [[Simple graph|simple]] undirected graphs as they require repeating the same edge twice, which violates the definition of [[Simple graph|simple]].}}

{{term|digraph}}
{{defn|Synonym for [[directed graph]].<ref name="clrs"/>}}

{{term|dipath}}
{{defn|See {{gli|directed path}}.}}

{{term|direct predecessor}}
{{defn|The tail of a directed edge whose head is the given vertex.}}

{{term|direct successor}}
{{defn|The head of a directed edge whose tail is the given vertex.}}

{{term|directed}}
{{defn|A [[directed graph]] is one in which the edges have a distinguished direction, from one vertex to another.<ref name="clrs"/> In a [[mixed graph]], a directed edge is again one that has a distinguished direction; directed edges may also be called arcs or arrows.}}

{{term|directed arc}}
{{defn|See {{gli|arrow}}.}}

{{term|directed edge}}
{{defn|See {{gli|arrow}}.}}

{{term|directed line}}
{{defn|See {{gli|arrow}}.}}

{{term|directed path}}
{{defn|A {{gli|path}} in which all the ''{{gli|edge}}s'' have the same {{gli|direction}}. If a directed path leads from {{gli|vertex}} {{math|''x''}} to vertex {{math|''y''}}, {{math|''x''}} is a {{gli|predecessor}} of {{math|''y''}}, {{math|''y''}} is a {{gli|successor}} of  {{math|''x''}}, and {{math|''y''}} is said to be {{gli|reachable}} from {{math|''x''}}.}}

{{term|direction}}
{{defn|no=1|The [[asymmetric relation]] between two {{gli|adjacent}} {{gli|vertex|vertices}} in a {{gli|graph}}, represented as an {{gli|arrow}}.}}
{{defn|no=2|The asymmetric relation between two vertices in a {{gli|directed path}}.}}

{{term|disconnect}}
{{defn|Cause to be {{gli|disconnected}}.}}

{{term|disconnected}}
{{defn|Not {{gli|connected}}.}}

{{term|disjoint}}
{{defn|no=1|Two subgraphs are edge disjoint if they share no edges, and vertex disjoint if they share no vertices.}}
{{defn|no=2|The disjoint union of two or more graphs is a graph whose vertex and edge sets are the [[disjoint union]]s of the corresponding sets.}}

{{term|dissociation number}}
{{defn|A subset of vertices in a graph ''G'' is called ''dissociation'' if it induces a [[Glossary of graph theory#subgraph|subgraph]] with maximum [[Degree (graph theory)|degree]] 1.}}

{{term|distance}}
{{defn|The [[Distance (graph theory)|distance]] between any two vertices in a graph is the length of the shortest path having the two vertices as its endpoints.}}

{{term|domatic}}
{{defn|A domatic partition of a graph is a partition of the vertices into dominating sets. The [[domatic number]] of the graph is the maximum number of dominating sets in such a partition.}}

{{term|dominating}}
{{defn|A [[dominating set]] is a set of vertices that includes or is adjacent to every vertex in the graph; not to be confused with a vertex cover, a vertex set that is incident to all edges in the graph. Important special types of dominating sets include independent dominating sets (dominating sets that are also independent sets) and connected dominating sets (dominating sets that induced connected subgraphs). A single-vertex dominating set may also be called a universal vertex. The domination number of a graph is the number of vertices in the smallest dominating set.}}

{{Term|dual}}{{Defn|A [[dual graph]] of a plane graph {{mvar|G}} is a graph that has a vertex for each face of {{mvar|G}}.}}{{glossary end}}