TUTCRIS - Tampereen teknillinen yliopisto

TUTCRIS

A computational approach to construct a multivariate complete graph invariant

Tutkimustuotosvertaisarvioitu

Yksityiskohdat

AlkuperäiskieliEnglanti
Sivut200-208
Sivumäärä9
JulkaisuInformation Sciences
Vuosikerta260
DOI - pysyväislinkit
TilaJulkaistu - 1 maaliskuuta 2014
OKM-julkaisutyyppiA1 Alkuperäisartikkeli

Tiivistelmä

In this paper, we present a computational approach for finding complete graph invariants. Specifically, we generate exhaustive sets of connected, non-isomorphic graphs with 9 and 10 vertices and demonstrate that a 97-dimensional multivariate graph invariant is capable to distinguish each of the non-isomorphic graphs. Furthermore, in order to tame the computational complexity of the problem caused by the vast number of graphs, e.g., involving over 10 million networks with 10 vertices, we suggest a low-dimensional, iterative procedure that is based on highly discriminative individual graph invariants. We show that also this computational approach leads to a perfect discrimination. Overall, our numerical results prove the existence of such graph invariants for networks with 9 and 10 vertices. Furthermore, we show that our iterative approach has a polynomial time complexity.