TOPICS
Search

Empty Graph


EmptyGraphs

An empty graph on n nodes consists of n isolated nodes with no edges. Such graphs are sometimes also called edgeless graphs or null graphs (though the term "null graph" is also used to refer in particular to the empty graph on 0 nodes).

The empty graph on 0 nodes is (sometimes) called the null graph and the empty graph on 1 node is called the singleton graph. The empty graph on n vertices is the graph complement of the complete graph K_n, and is commonly denoted K^__n. The notation O_n is apparently also used by some authors (e.g., Tyshkevich 2000, Fact 2), but not recommended as it conflicts with use of this notation for an odd graph among others.

The empty graph on n nodes can be generated in the Wolfram Language as Graph[Range[n], {}] or FromEntity[Entity["Graph", {"Empty", n]}], and precomputed properties of empty graphs are available in the Wolfram Language using GraphData[{"Empty", n}].

The bipartite double graph of the empty graph K^__n is K^__(2n).

Empty graphs are (trivially) dominating unique.


See also

Complete Graph, Graph, Null Graph, Singleton Graph

Explore with Wolfram|Alpha

References

Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 141, 1990.Tyshkevich, R. "Decomposition of Graphical Sequences and Unigraphs." Disc. Math. 220, 201-238, 2000.

Referenced on Wolfram|Alpha

Empty Graph

Cite this as:

Weisstein, Eric W. "Empty Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/EmptyGraph.html

Subject classifications