Research Article: The Uniqueness of -Matrix Graph Invariants

Date Published: January 2, 2014

Publisher: Public Library of Science

Author(s): Matthias Dehmer, Yongtang Shi, Frank Emmert-Streib.


In this paper, we examine the uniqueness (discrimination power) of a newly proposed graph invariant based on the matrix defined by Randić et al. In order to do so, we use exhaustively generated graphs instead of special graph classes such as trees only. Using these graph classes allow us to generalize the findings towards complex networks as they usually do not possess any structural constraints. We obtain that the uniqueness of this newly proposed graph invariant is approximately as low as the uniqueness of the Balaban index on exhaustively generated (general) graphs.

Partial Text

Matrix-based descriptors have been developed extensively [1]–[3]. As a result, the distance matrix, the adjacency matrix and other graph-theoretical matrices [4] have been used to define topological graph measures and to examine their properties [4], [5]. A property which has been of considerable interest when designing topological descriptors is referred to as uniqueness [6]–[8]. Generally, the uniqueness of a structural graph measure relates to the ability to distinguish the structure of non-isomorphic graphs uniquely. From a mathematical point of view, the low uniqueness or high degeneracy of a graph measure under consideration is an undesired aspect as non-isomorphic graphs should be mapped to non-equal values. Such a highly discriminating graph invariant could be then used to distinguish graph structures uniquely and, thus, to perform graph isomorphism testing [9], [10]. In the context of graph isomorphism testing, so-called complete graph invariants have been investigated [9], [11]. Such a graph invariant has the property that it discriminates all non-isomorphic graphs uniquely (i.e., without any degeneracy) and isomorphic graphs are mapped to equal values [9], [11]. For example, Liu and Klein [11] made an attempt to derive complete graph invariants by using eigenvalues. Dehmer et al. [8], [9] defined graph entropies which turned out to be the most discriminative measures so far when using exhaustively generated graphs. Clearly, such measures are suitable candidates to test graph isomorphism efficiently [9].

Before interpreting Table 1, we explain its notation. We here used the graph classes , [8] and , [8]. Again is the class of all exhaustively generated non-isomorphic and connected graphs with vertices [8]. is the class of exhaustively generated non-isomorphic and connected alkane trees [8]. ndv stands for the number of non-distinguishable values [8] and where is a class of graphs, see [7].

This paper investigated the uniqueness of the recently developed topological index introduced by Randić et al. [2]. has been defined quite similarly as it is based on the novel matrix instead of . Based on small tests and by only using example graphs, Randić et al. [2] hypothesized has higher uniqueness than and, the index which combined with index , may suffice to resolve the graph isomorphism issue for most cases of molecular graphs.