Uniquely describing a graph According to answers here https://math.stackexchange.com/questions/1524598/a-general-incidence-problem// an unigraph comes from unigraphic degree sequences if it can be uniquely determined by its degree sequences.
Adjacency matrix or incidence matrix of a graph provides every computable information about a graph.
Apart from degree sequences what additional information would one need to provide to capture any graph uniquely? 
That is degree sequence plus some additional information should give as much information on a graph as possible. What is this additional information? 
Adjacency matrix needs about $2 n^2\log n$ bits of information (to specify a row and column you need to spend $\log n + \log n$ bits and we have $n^2$ combinations of rows and columns). If we choose to represent a graph by fixing an order on vertices, you still need $n^2$ bits (same as adjacency matrix).
Degree sequences need about $n\log n$ bits of information.
So we are missing a factor of $2n$ or $\frac n{\log n}$ depending on how we look. 
It is clear degree sequences are insufficient. Information theoretically we need to provide incidence relations. Is there a way to specify this information implicitly so that a multiplicative factor of $n$ is taken care of while we do not add additionally the degree information?

That is can we separate the degree information from this additional multiplicative piece? Is there a meaning to this multiplicative factor? Thinking of indices and conditional entropies only gives you additive meaning. This means you get only quadratic factors back.
 A: I'll address the question like this: if you are given the degree sequence of a graph, what is the most number of additional bits that you might need to provide to uniquely identify the graph?
The answer to this depends on how many graphs can have the same degree sequence, and also on whether labelled graphs or isomorphism classes are being considered.
As far as I'm aware, it is not known which degree sequence has the most graphs in either case.  For labelled graphs, when you know the labelled degree sequence and you don't count permutations of it as being the same, there is some evidence that for large enough $n$ sequences close to $\frac{n-1}2,\frac{n-1}2,\ldots,\frac{n-1}2$ will win (I'm not allowing loops). The number of labelled graphs with any given degree sequence like that is asymptotically
$$\Theta(1) \frac{2^{n^2/2}}{\pi^{n/2}n^{n/2}},$$
see this paper. So in this case you can get by with
$$\frac{n^2}2 - \frac{n\log_2 (\pi n)}2 + O(1)$$
bits and this is a lower bound on how many bits might be needed in the worst case.  If computational complexity is ignored, the information can be provided in that many bits by giving an index number ("the $i$-th graph with the given degree sequence"). 
