{{Short description|Type of graph}} An '''unigraph''' or '''unigraphic graph''' is a graph that is up to isomorphism defined by its degree sequence. In other words, if any two graphs with the same given degree sequence are isomorphic to each other then they are (representations of) the same unigraph. The corresponding degree sequence is called '''unigraphical'''.<ref name=rety>Regina Tyshkevich, "Decomposition of graphical sequences and unigraphs", ''Discrete Mathematics'' 220 (2000) 201–238</ref><ref name=mawo>[https://mathworld.wolfram.com/UnigraphicGraph.html Unigraphic Graph], Wolfram MathWorld</ref>
For unlabelled graphs it is natural to operate with degree sequences ordered in the decreasing or increasing order.<ref name=rety/>
Properties of unigraphical sequences were studied in mid-1970s by Kleitman and others.<ref name=rety/> An algorithm for recognizing unigraphicity in linear time was provided by Kleitman and Li in 1975.<ref>Kleitman, D. J. and Li, S.-Y. "A Note on Unigraphic Sequences." Stud. Appl. Math. 54, 283-287, 1975.</ref>
One may readily find that all graphs on less than five vertices are unigraphs. An example of a non-unigraphic pair on 5 vertices are path graph on 5 vertices and the union of the 3-vertex and 2-vertex complete graphs, both of which having the degree sequence (2,2,2,1,1).<ref name=mawo/>
A series of papers by Regina Tyshkevich and her student, Arkady Chernyak, described the complete characterization of unigraphs, which was summarized in her 2000 paper.<ref name=rety/> The characterization is done in terms of what is now called "Tyshkevich decomposition".<ref name=mawo/><ref>Christine T. Cheng, "Tyshkevich's graph decomposition and the distinguishing numbers of unigraphs", ''Discrete Mathematics'', Volume 348, Issue 8, 2025, {{doi|10.1016/j.disc.2025.114492}}</ref>
==References== {{reflist}}
Category:Graph families