Connected Permutations of Vertices for Canonical Form Detection in Graph Mining

Andrés Gago-Alonso


Checking redundancies is one of the most significant tasks in graph mining. Canonical forms of graphs are widely used to guarantee and speed up this kind of task. In general, canonical form calculation requires to orderly check partial or complete prefixes of vertex permutations for picking up the codification to unambiguously represent a graph. In this paper, novel theoretical results are introduced for reducing the number of candidate prefixes to a specific subset associated with connected permutations. Furthermore, several interesting mathematical properties are also described and proved, including strong linkages among graph mining, discrete mathematics, and different kinds of canonical forms. Although this paper does not declare a scheme for directly reducing the complexity of finding canonical descriptions, our contributions can open novel opportunities for future improvements in graph mining by interrelating concepts from different existing approaches.

Palabras clave

canonical form; graph isomorphism; connected permutation; adjacency matrix; spanning tree

Texto completo:

PDF (English)

Enlaces refback

  • No hay ningún enlace refback.


La Universidad de las Ciencias Informáticas (UCI), a través del sello editorial Ediciones Futuro, publica los contenidos de la Revista Cubana de Ciencias Informáticas (RCCI) bajo licencia Creative Commons de tipo Atribución 4.0 Internacional (CC BY 4.0). Esta licencia permite a otros distribuir, mezclar, ajustar y construir a partir de su obra, incluso con fines comerciales, siempre que le sea reconocida la autoría de la creación original. Saber más