Null graph

From Wikipedia, the free encyclopedia
  (Redirected from Empty graph)
Jump to: navigation, search

In the mathematical field of graph theory, the 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 of order zero (having zero vertices). As a consequence, it also has zero edges. In some contexts, K_0 is excluded from being considered a graph (either by definition, or more simply as a matter of convenience).

The order-zero graph is the initial object in the category of graphs, according to some definitions of a category of graphs. Its inclusion within the definition of graph theory is more useful in some contexts than others. On the positive side, K_0 follows naturally from the usual set-theoretic definitions of a graph (it is the ordered pair of empty sets), and 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, most well-defined formulas for graph properties must include exceptions for K_0 if it is included as a graph ("counting all strongly connected components of a graph" would become "counting all non-null strongly connected components of a graph"). Due to the undesirable aspects, it is usually assumed in literature that the term "graph" implies "graph with at least one vertex" unless context suggests otherwise.[1][2]

When acknowledged, K_0 fulfills (vacuously) most of the same basic graph properties as K_1 (the graph with one vertex and no edges): it has a size of zero, it is equal to its complement graph (\bar K_0), it is a connected component (namely, \forall x \isin V : \forall y \isin V : \exists \text{path}(x,y)), a forest, and a planar graph. It may be an undirected graph or a directed graph (or even both); when considered as directed, it is a directed acyclic graph, and it is both a complete graph and an empty graph (just to name a few). 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 \bar K_n

For each natural number n, the edgeless graph (or empty graph) \bar K_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.[3][4]

The n-vertex edgeless graph is the complement graph for the complete graph K_n, and therefore it is commonly denoted as \bar 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.