Recognition of Unigraphs through Superposition of Graphs
Alessandro Borri, Tiziana Calamoneri, and Rossella Petreschi
Vol. 15, no. 3, pp. 323-343, 2011. Regular paper.
Abstract Unigraphs are graphs uniquely determined by their own degree sequence up to isomorphism. In this paper a structural description for unigraphs is introduced: vertex set is partitioned into three disjoint sets while edge set is divided into two different classes. This characterization allows us to design a new linear time recognition algorithm that works recursively pruning the degree sequence of the graph. The algorithm detects two particular graphs whose superposition generates the given unigraph.
Submitted: May 2009.
Reviewed: January 2010.
Revised: March 2010.
Accepted: October 2010.
Final: October 2010.
Published: July 2011.
Communicated by Sandip Das and Ryuhei Uehara
article (PDF)