Geodesic
An alternative way of defining finite graphs
Prikladnaâ diskretnaâ matematika, no. 3 (2015), pp. 83-94.

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

In this paper, we consider the graph linear notation – a complete graph invariant, which is positioned as an alternative to description of finite graphs. This invariant is constructed using an algorithm which is close to the search algorithm for canonical forms of graphs. The storage in a memory of a graph linear notation instead of the graph itself simplifies the procedures for constructing graph illustrations and testing two graphs for isomorphism. We demonstrate how the main graph theory concepts including colouring and graph paths can be defined in terms of graph linear notations.
Mots-clés : graph isomorphism, graph invariants.
Keywords: automorphism classes of vertices and edges 
@article{PDM_2015_3_a6,
     author = {M. N. Nazarov},
     title = {An alternative way of defining finite graphs},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {83--94},
     publisher = {mathdoc},
     number = {3},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2015_3_a6/}
}
TY  - JOUR
AU  - M. N. Nazarov
TI  - An alternative way of defining finite graphs
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2015
SP  - 83
EP  - 94
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2015_3_a6/
LA  - ru
ID  - PDM_2015_3_a6
ER  - 
%0 Journal Article
%A M. N. Nazarov
%T An alternative way of defining finite graphs
%J Prikladnaâ diskretnaâ matematika
%D 2015
%P 83-94
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2015_3_a6/
%G ru
%F PDM_2015_3_a6
M. N. Nazarov. An alternative way of defining finite graphs. Prikladnaâ diskretnaâ matematika, no. 3 (2015), pp. 83-94. http://geodesic.mathdoc.fr/item/PDM_2015_3_a6/

[1] Nazarov M. N., “Alternative approaches to the description of classes of isomorphic graphs”, Prikladnaya diskretnaya matematika, 2014, no. 3, 86–97 (in Russian)

[2] Zykov A. A., Basics of Graph Theory, Vuzovskaya Kniga Publ., Moscow, 2004, 664 pp. (in Russian)

[3] 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

[4] Belov V. V., Vorob'ev E. M., Shatalov V. E., Graph Theory, Vysshaya Shkola Publ., Moscow, 1976, 391 pp. (in Russian)

[5] Brecher J., “Graphical representation of stereochemical configuration”, Pure Appl. Chem., 78:2 (2006), 1897–1970

[6] Kharari F., Graph Theory, KomKniga Publ., Moscow, 2006, 296 pp. (in Russian)

[7] Harary F., Palmer E. M., Graphical Enumeration, Academic Press, N.Y., 1973, 240 pp. | MR | Zbl

[8] Zykov A. A., “Hypergraphs”, Russian Mathematical Surveys, 29:6 (1974), 89–156 | DOI | MR | Zbl