|
Applied Graph Theory
An alternative way of defining finite graphs
M. N. Nazarov National Research University of Electronic Technology, Moscow, Russia
Abstract:
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.
Keywords:
graph isomorphism, automorphism classes of vertices and edges, graph invariants.
Citation:
M. N. Nazarov, “An alternative way of defining finite graphs”, Prikl. Diskr. Mat., 2015, no. 3(29), 83–94
Linking options:
https://www.mathnet.ru/eng/pdm514 https://www.mathnet.ru/eng/pdm/y2015/i3/p83
|
Statistics & downloads: |
Abstract page: | 397 | Full-text PDF : | 181 | References: | 45 |
|