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 have 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 $\Theta(m\log n)$ for numbered graphs, $\Theta(n+(m-n+1)\log n)$ for unnumbered graphs with the number of vertices $n$ and the number of edges $m$, and $\Theta(n^2\log n)$ 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(n\log (n\Delta))$ or $O(n\log\Delta)$ size, respectively, where $\Delta$ is the maximum vertex degree.