Unigraph

An unigraph or unigraphic graph is a graph that is up to isomorphism defined by its degree sequence. In other words, any two grtaphs with the same degree sequence are isomorphic to each other. 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 characterizatrion is done in terms of what is now called "Tyshkevich decomposition".^[2][4]