Home | Issues | About JGAA | Instructions for Authors |
Special Issue on Selected Papers from the Third Annual Workshop on Algorithms and Computation (WALCOM 2009)
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.
|
Submitted: May 2009.
Reviewed: January 2010.
Revised: March 2010.
Accepted: October 2010.
Final: October 2010.
Published: July 2011.
|
Journal Supporters
|