Proceedings of ISP RAS


Size of the memory for storage of ordered rooted graph

I. Burdonov (ISP RAS, Moscow, Russia)
A. Kossatchev (ISP RAS, Moscow, Russia)

Abstract

The paper considers boundaries of memory necessary and sufficient for storage of undirected ordered rooted connected graphs, both numbered and unnumbered. The introduction contains the basic definitions and the problem statement. A graph is rooted if one of its vertices is marked as a root. A graph is ordered if for each of its vertices all the incident edges are ordered (numbered). A graph is numbered if all its vertices are numbered with different integer numbers (from 0 to n-1, where n is the number of vertices). Two undirected ordered graphs G and G` are weakly isomorphic if there exists a one-to-one correspondence between their vertices, for which corresponding vertices has the same degrees (numbers of incident edges) and two edges having corresponding ends and the same numbers in these ends, also have the other ends corresponding. Isomorphism of rooted graphs should also correspond their roots. Isomorphism of numbered graphs should also correspond the vertices with the same numbers. Graphs are considered up to weak isomorphism. It is shown that the memory necessary and sufficient for storage of any graph has the size Θ(mlogn) for numbered graphs, Θ(n+(m n+1)logn) for unnumbered graphs with the number of vertices n and the number of edges m, and Θ(n2logn) for graphs without multiple edges and loops with the number of vertices n. It is also shown that the memory sufficient for storage of an edge sequence of length O(n) or a spanning tree, has the O(nlog(nΔ)) or O(nlogΔ) size, respectively, where Δ is the maximum vertex degree.

Keywords

undirected graphs; ordered graph; labeled graph; rooted graph; graph representation; graph enumeration

Edition

Proceedings of the Institute for System Programming, vol. 29, issue 2, 2017, pp. 7-26.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2017-29(2)-1

Full text of the paper in pdf (in Russian) Back to the contents of the volume