Lesson plan
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. 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".
Article summary
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".
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.