Geodesic
Alternative approaches to the description of classes of isomorphic graphs
Prikladnaâ diskretnaâ matematika, no. 3 (2014), pp. 86-97.

Voir la notice de l'article provenant de la source Math-Net.Ru

An algorithm for natural indexing of automorphic equivalence classes of vertices and edges in finite graphs is proposed. Using this indexing, the alternative description of graph isomorphism classes is constructed. It is also demonstrated that one can apply such classical concepts as colouring, operations on graphs and subgraphs to the graph isomorphism classes.
Mots-clés : graph isomorphism, graph invariants.
Keywords: automorphic equivalence classes of vertices, automorphic equivalence classes of edges 
@article{PDM_2014_3_a7,
     author = {M. N. Nazarov},
     title = {Alternative approaches to the description of classes of isomorphic graphs},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {86--97},
     publisher = {mathdoc},
     number = {3},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2014_3_a7/}
}
TY  - JOUR
AU  - M. N. Nazarov
TI  - Alternative approaches to the description of classes of isomorphic graphs
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2014
SP  - 86
EP  - 97
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2014_3_a7/
LA  - ru
ID  - PDM_2014_3_a7
ER  - 
%0 Journal Article
%A M. N. Nazarov
%T Alternative approaches to the description of classes of isomorphic graphs
%J Prikladnaâ diskretnaâ matematika
%D 2014
%P 86-97
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2014_3_a7/
%G ru
%F PDM_2014_3_a7
M. N. Nazarov. Alternative approaches to the description of classes of isomorphic graphs. Prikladnaâ diskretnaâ matematika, no. 3 (2014), pp. 86-97. http://geodesic.mathdoc.fr/item/PDM_2014_3_a7/

[1] Diestel R., Graph Theory, 3rd edition, Springer Verlag, Heidelberg, 2005, 451 pp. | MR | Zbl

[2] Belov V. V., Vorobev E. M., Shatalov V. E., Teoriya grafov, Vysshaya shkola, M., 1976, 391 pp. | Zbl

[3] Zykov A. A., Osnovy teorii grafov, Nauka, M., 1987, 383 pp. | MR | Zbl

[4] Holmes M. R., Elementary Set Theory with a Universal Set, Academia, Louvain-la-Neuve, 1998, 241 pp. | MR | Zbl

[5] Aloul F. A., Ramani A., Markov I. L., Sakallah K. A., “Solving difficult instances of Boolean satisfiability in the presence of symmetry”, IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, 22:9 (2003), 1117–1137 | DOI

[6] Darga P., Sakallah K., Markov I. L., “Faster symmetry discovery using sparsity of symmetries”, Proc. 45st Design Automation Conference, ACM, N.Y., 2008, 149–154

[7] Flarri R., Gruppy simmetrii. Teoriya i khimicheskie prilozheniya, Mir, M., 1983, 400 pp.

[8] Bonchev D., Rouvray D. H., Chemical Graph Theory: Introduction and Fundamentals, Gordon and Breach science publishers, N.Y., 1991, 300 pp. | Zbl

[9] King R., Khimicheskie prilozheniya topologii i teorii grafov, Mir, M., 1987, 560 pp.

[10] Sparrow M. K., “A linear algorithm for computing automorphic equivalence classes: the numerical signatures approach”, Social Networks, 15 (1993), 151–170 | DOI | MR

[11] Southwell R., Finding Symmetries in Graphs, Ph. D. thesis, University of York, UK, 2006, 109 pp.

[12] Katebi H., Sakallah K., Markov I. L., “Graph symmetry detection and canonical labelling: differences and synergies”, Proc. Turing-100, EPIC, 10, 2012, 181–195

[13] Weininger D., Weininger A., Weininger J., “SMILES. 2. Algorithm for generation of unique SMILES notation”, J. Chem. Inf. Comput. Sci., 29:2 (1989), 97–101 | DOI

[14] Kharari F., Teoriya grafov, KomKniga, M., 2006, 296 pp.

[15] Kobler J., Schoning U., Toran J., The Graph Isomorphism Problem: its Structural Complexity, Birkhauser, Berlin, 1993, 160 pp. | MR | Zbl

[16] Harary F., “A survey of the reconstruction conjecture”, Graphs and Combinatorics, Lecture Notes in Mathematics, 406, 1974, 18–28 | DOI | MR | Zbl