Unigraph
An unigraph or unigraphic graph is a graph that is up to isomorphism defined by its degree sequence.
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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.
For unlabelled graphs it is natural to operate with degree sequences ordered in the decreasing or increasing order. Properties of unigraphical sequences were studied in mid-1970s by Kleitman and others. An algorithm for recognizing unigraphicity in linear time was provided by Kleitman and Li in 1975.
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).
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. The characterization is done in terms of what is now called "Tyshkevich decomposition".
Text derived from https://en.wikipedia.org/w/index.php?oldid=1328261486 under CC BY-SA 4.0; modifications have been made.