Unigraph
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.[1][2]
For unlabelled graphs it is natural to operate with degree sequences ordered in the decreasing or increasing order.[1]
Properties of unigraphical sequences were studied in mid-1970s by Kleitman and others.[1] An algorithm for recognizing unigraphicity in linear time was provided by Kleitman and Li in 1975.[3]
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).[2]
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.[1] The characterization is done in terms of what is now called "Tyshkevich decomposition".[2][4]
References
[edit]- ^ a b c d Regina Tyshkevich, "Decomposition of graphical sequences and unigraphs", Discrete Mathematics 220 (2000) 201–238
- ^ a b c Unigraphic Graph, Wolfram MathWorld
- ^ Kleitman, D. J. and Li, S.-Y. "A Note on Unigraphic Sequences." Stud. Appl. Math. 54, 283-287, 1975.
- ^ 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