Null graph

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In the mathematical field of graph theory, the term "null graph" may refer either to the order-zero graph, or alternatively, to any edgeless graph (the latter is sometimes called an "empty graph").

Order-zero graph[edit]

Order-zero graph (null graph)
Vertices 0
Edges 0
Radius 0
Diameter 0
Girth \infty
Automorphisms 1
Chromatic number 0
Chromatic index 0
Genus 0
Properties Integral
Symmetric
Notation K_0

The order-zero graph, K_0, is the unique graph having no vertices (hence its order is zero). It follows that K_0 also has no edges. Some authors exclude K_0 from consideration as a graph (either by definition, or more simply as a matter of convenience). Whether including K_0 as a valid graph is useful depends on context. On the positive side, K_0 follows naturally from the usual set-theoretic definitions of a graph (it is the ordered pair (V, E) for which the vertex and edge sets, V and E, are both empty), in proofs it serves as a natural base case for mathematical induction, and similarly, in recursively defined data structures K_0 is useful for defining the base case for recursion (by treating the null tree as the child of missing edges in any non-null binary tree, every non-null binary tree has exactly two children). On the negative side, including K_0 as a graph requires that many well-defined formulas for graph properties include exceptions for it (for example, "counting all strongly connected components of a graph" becomes "counting all non-null strongly connected components of a graph"). To avoid the need for such exceptions, it is often assumed in literature that the term graph implies "graph with at least one vertex" unless context suggests otherwise.[1][2]

In category theory, the order-zero graph is, according to some definitions of "category of graphs," the initial object in the category.

K_0 does fulfill (vacuously) most of the same basic graph properties as does K_1 (the graph with one vertex and no edges). As some examples, K_0 is of size zero, it is equal to its complement graph \overline{K_0}, it is a connected component, a forest, and a planar graph. It may be considered undirected, directed, or even both; when considered as directed, it is a directed acyclic graph. And it is both a complete graph and an edgeless graph. However, definitions for each of these graph properties will vary depending on whether context allows for K_0.

Edgeless graph[edit]

Edgeless graph (empty graph, null graph)
Vertices n
Edges 0
Radius 0
Diameter 0
Girth \infty
Automorphisms n!
Chromatic number 1
Chromatic index 0
Genus 0
Properties Integral
Symmetric
Notation \overline K_n

For each natural number n, the edgeless graph (or empty graph) \overline K_n of order n is the graph with n vertices and zero edges. An edgeless graph is occasionally referred to as a null graph in contexts where the order-zero graph is not permitted.[1][2]

The notation \overline K_n arises from the fact that the n-vertex edgeless graph is the complement of the complete graph K_n.

See also[edit]

Notes[edit]

References[edit]

  • Harary, F. and Read, R. (1973), "Is the null graph a pointless concept?", Graphs and Combinatorics (Conference, George Washington University), Springer-Verlag, New York, NY.