Special Issue on Selected Papers from the Third Annual Workshop on Algorithms and Computation (WALCOM 2009)
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)