Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00229 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.
|
Published: July 2011. Revised: March 2010. Accepted: October 2010. Final: October 2010. Reviewed: January 2010. Submitted: May 2009. Communicated by Sandip Das and Ryuhei Uehara |
| Journal of Graph Algorithms and Applications |