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.
2011
01 Pubblicazione su rivista::01a Articolo in rivista
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]
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/482214
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? ND
social impact