TOPICS
Search

Unigraphic Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A unigraphic graph (or simply a "unigraph") is a graph that is isomorphic to every graph having that degree sequence. All graphs on four are fewer vertices are unigraphic.

The numbers of unigraphs on n=1, 2, ... nodes are 1, 2, 4, 11, 28, 72, 170, 407, 956, 2252 ... (OEIS A122423), and the numbers of these that are connected are 1, 1, 2, 6, 16, 42, 96, 234, 546, 1292, ... (OEIS A365548). The numbers of connected graphs that have distinct degree sequences among all connected graphs with n nodes for n=1, 2, ... are 1, 1, 1, 2, 6, 17, 45, 99, 238, 549, 1296, ... (OEIS A309757).

There are therefore 6 graphs on 5 vertices which are not unigraphic, including the path graph P_5 and P_2+C_3 which share the degree sequence (2,2,2,1,1).

If a graph G is a unigraph, then its graph complement G^_ is also a unigraph (Barrus et al. 2023).

An algorithm for recognizing unigraphicity in linear time is described by Kleitman (1975). While the class of unigraphs has no forbidden induced subgraph characterization, it can be characterized via decomposition (Barrus et al. 2023). In particular, a graph G is a unigraph iff each component of its Tyshkevich decomposition is a unigraph (Tyshkevich 2000, Barrus et al. 2023).

The only regular unigraphs are the complete graphs K_n, empty graphs K^__n, ladder rung graphs mK_2, cocktail party graphs mK_2^_, and the cycle graph C_5 (Johnson 1975, Koren 1976, Tyshkevich 2000).

See also

Degere Sequence, Graphic Sequence, Vertex Degree

Explore with Wolfram|Alpha

References

Barrus, M. D.; Trenk, A. N.; and Whitman, R. "The Hereditary Closure of the Unigraphs." 23 Aug 2023. https://arxiv.org/abs/2308.12190Johnson, R. H. "Simple Separable Graphs." Pacific J. Math. 56, 143-158, 1975.Kleitman, D. J. and Li, S.-Y. "A Note on Unigraphic Sequences." Stud. Appl. Math. 54, 283-287, 1975.Koren, M. "Pairs of Sequences with a Unique Realization by Bipartite Graphs." J. Combin. Th. Ser. B 21, 224-234, 1976.Koren, M. "Sequences with a Unique Realization by Simple Graphs." J. Combin. Th. Ser. B 21, 235-244, 1976.Li, S.-Y. R. "Graphic Sequences with Unique Realizations." J. Combin. Th. Ser. B 19, 42-68, 1975.Sloane, N. J. A. Sequences A122423, A309757, and A365548 in "The On-Line Encyclopedia of Integer Sequences."Tyshkevich, R. "The Canonical Decomposition of a Graph." Dokl. Akad. Nauk. BSSR 24, 677-679, 1980.Tyshkevich, R. "Decomposition of Graphical Sequences and Unigraphs." Disc. Math. 220, 201-238, 2000.

Cite this as:

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

Subject classifications