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.

UDC: 519.171+519.175.1+519.175

DOI: 10.17223/20710410/29/7

Bibliographic databases:

•