Unigraphic Graph

A unigraphic graph (or simply a "unigraph") is a finite simple graph that is isomorphic to every finite simple graph having that degree sequence. All graphs on four or fewer vertices are unigraphic. The numbers of nonisomorphic unigraphs on , 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 nodes for , 2, ... are 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 and which share the degree sequence . If a graph is a unigraph, then its graph complement is also a unigraph (Barrus et al. 2025). An algorithm for recognizing unigraphicity in linear time is described by Kleitman and Li (1975). While the class of unigraphs has no forbidden induced subgraph characterization, it can be characterized via decomposition (Barrus et al. 2025). In particular, a graph is a unigraph iff each factor in its Tyshkevich decomposition is a unigraph (Tyshkevich 2000, Barrus et al. 2025). The only regular unigraphs are the complete graphs , empty graphs , ladder rung graphs , cocktail party graphs , and the cycle graph (Johnson 1975, Koren 1976, Tyshkevich 2000).