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 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.
Recognition of Unigraphs through Superposition of Graphs / A., Borri; Calamoneri, Tiziana; Petreschi, Rossella. - STAMPA. - 5431:(2009), pp. 165-176. (Intervento presentato al convegno 3rd International Workshop on Algorithms and Computation tenutosi a Calcutta, INDIA nel FEB 18-20, 2009) [10.1007/978-3-642-00202-1_15].
Recognition of Unigraphs through Superposition of Graphs
CALAMONERI, Tiziana;PETRESCHI, Rossella
2009
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 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
