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.
Download file
Counter downloads: 291
- Title An alternative way of defining finite graphs
- Headline An alternative way of defining finite graphs
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 3(29)
- Date:
- DOI
Keywords
изоморфизм графов, классы автоморфизма вершин и рёбер, инварианты графов, graph isomorphism, automorphism classes of vertices and edges, graph invariantsAuthors
References
Назаров М. Н. Альтернативные подходы к описанию классов изоморфных графов // Прикладная дискретная математика. 2014. №3. С. 86-97.
Зыков А. А. Основы теории графов. М.: Вузовская книга, 2004. 664с.
Weininger D., Weininger A., and Weininger J. SMILES. 2. Algorithm for generation of unique SMILES notation // J. Chem. Inf. Comput. Sci. 1989. V.29. No. 2. P. 97-101.
Белов В. В., Воробьев Е. М., Шаталов В. Е. Теория графов. М.: Высшая школа, 1976. 391 с.
Brecher J. Graphical representation of stereochemical configuration // Pure Appl. Chem. 2006. V. 78. No. 2. P. 1897-1970.
Харари Ф. Теория графов. М.: КомКнига, 2006. 296с.
Harary F. and Palmer E. M. Graphical Enumeration. N.Y.: Academic Press, 1973. 240 p.
Zykov A. A. Hypergraphs // Russian Mathematical Surveys. 1974. V.29. P.89-154.
An alternative way of defining finite graphs | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2015. № 3(29).
Download full-text version
Counter downloads: 1012