Unigraphs are graphs uniquely determined by their own degree se- quence 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 re- cursively pruning the degree sequence of the graph. The algorithm detects two particular graphs whose superposition generates the given unigraph.
Recognition of unigraphs through superposition of graphs / Alessandro, Borri; Calamoneri, Tiziana; Petreschi, Rossella. - In: JOURNAL OF GRAPH ALGORITHMS AND APPLICATIONS. - ISSN 1526-1719. - 15:3(2011), pp. 323-343. [10.7155/jgaa.00229]
Recognition of unigraphs through superposition of graphs
CALAMONERI, Tiziana;PETRESCHI, Rossella
2011
Abstract
Unigraphs are graphs uniquely determined by their own degree se- quence 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 re- cursively pruning the degree sequence of the graph. The algorithm detects two particular graphs whose superposition generates the given unigraph.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.