Size of the memory for storage of ordered rooted graph

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 Q( mlogn ) for numbered graphs, Q( n +( m - n +1) logn ) for unnumbered graphs with the number of vertices n and the number of edges m , and Q( n² logn ) 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 D)) or O ( nlog D) size, respectively, where D is the maximum vertex degree.

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

1. O.Ore. Theory of graphs. AMS, Providence, Rhode Island, 1962.

2. F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973.

3. The On-Line Encyclopedia of Integer Sequences. Catalan numbers. https://oeis.org/A000108. Accessed 10.02.2017.

4. J. H. Conway and R. K. Guy. The Book of Numbers, New York: Springer-Verlag, 1995.

5. F. Bergeron, G. Labelle and P. Leroux. Combinatorial Species and Tree-like Structures, EMA vol.67, Cambridge, 1998.

6. R. Dutton, and R. Brigham. Computationally Efficient. Bounds for the Catalan Numbers. Europ. J. Combinatorics, vol.7, 1986.

7. The solution of mathematics online, http://math24.biz/. Accessed 10.02.2017.