Tampere University of Technology

TUTCRIS Research Portal

A computational approach to construct a multivariate complete graph invariant

Research output: Contribution to journalArticleScientificpeer-review

Details

Original languageEnglish
Pages (from-to)200-208
Number of pages9
JournalInformation Sciences
Volume260
DOIs
Publication statusPublished - 1 Mar 2014
Publication typeA1 Journal article-refereed

Abstract

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.

Keywords

  • Information inequality, Quantitative graph theory, Random network model, Statistics