Return to Answer

Each graph can be uniquelly represented as an adjacency matrix. This is simply an nxn matrix of values 0,1. Each graph can therefore be expressed uniquely as a string of length n^2 by sequentially concatenating each line. Graphs with cycles and directed graphs are also uniquely represented.

Examples:
The complete graph of degree 3 can be expressed as 011-101-110 -> 011101110
The graph with Nodes {1,2,3} and edges {{1, 2},{1,3}} can be expressed as 011-100-100 -> 011100100

From this representation and from kolmogorov complexity certain statements become evident.

(1) For any other representation of graphs, there exists a constant c such that the conditional kolgomorov complexity on this representation saves at most c bits from the kolmogorov complexity from adjacency matrix.

(2) Sparse graphs are highly compressible (adjacency matrix of sparse graph contain a lot of zeroes versus very few ones)

(3) Program p1(n) := find the nth graph g such that no graph preceding (in my representation) is isomorphic,.
Program p2(n) := find the smallest graph that is isomorphic to the graph n.
program p3(n) := find the n' such that p1(n') = p2(n)
p3 is the function that compresses a graph

Each graph can be uniquelly represented as an adjacency matrix. This is simply an nxn matrix of values 0,1. Each graph can therefore be expressed uniquely as a string of length n^2 by sequentially concatenating each line. Graphs with cycles and directed graphs are also uniquely represented.

Examples:
The complete graph of degree 3 can be expressed as 011-101-110 -> 011101110
The graph with Nodes {1,2,3} and edges {{1, 2},{1,3}} can be expressed as 011-100-100 -> 011100100

From this representation and from kolmogorov complexity certain statements become evident.

(1) For any other representation of graphs, there exists a constant c such that the conditional kolgomorov complexity on this representation saves at most c bits from the kolmogorov complexity from adjacency matrix.

(2) Sparse graphs are highly compressible (adjacency matrix of sparse graph contain a lot of zeroes versus very few ones)

(3) if all you care about is about equivalency classes between graphs.
Program p1(n) := find the nth graph g such that no graph preceding (in my representation) is isomorphic,.
Program p2(n) := find the smallest graph that is isomorphic to the graph n.
program p3(n) := find the n' such that p1(n') = p2(n)
p3 is the function that compresses a graph
p1 is the decompression function

Each graph can be uniquelly represented as an adjacency matrix. This is simply an nxn matrix of values 0,1. Each graph can therefore be expressed uniquely as a string of length n^2 by sequentially concatenating each line. Graphs with cycles and directed graphs are also uniquely represented.

Examples:
The complete graph of degree 3 can be expressed as 011-101-110 -> 011101110
The graph with Nodes {1,2,3} and edges {{1, 2},{1,3}} can be expressed as 011-100-100 -> 011100100

From this representation and from kolmogorov complexity certain statements become evident.

(1) For any other representation of graphs, there exists a constant c such that the conditional kolgomorov complexity on this representation saves at most c bits from the kolmogorov complexity from adjacency matrix.

(2) Sparse graphs are highly compressible (adjacency matrix of sparse graph contain a lot of zeroes versus very few ones)

I hope this answers your question.

@Qiaochu Yuan My statements are concerned with kolmogorov complexity. In the case of graph isomorphism, we are only concerned with the matrices such that no permutation of lines can result in a smaller number. My statements are valid since they are all within the context of kolmogorov complexity.

Each graph can be uniquelly represented as an adjacency matrix. This is simply an nxn matrix of values 0,1. Each graph can therefore be expressed uniquely as a string of length n^2 by sequentially concatenating each line. Graphs with cycles and directed graphs are also uniquely represented.

Examples:
The complete graph of degree 3 can be expressed as 011-101-110 -> 011101110
The graph with Nodes {1,2,3} and edges {{1, 2},{1,3}} can be expressed as 011-100-100 -> 011100100

From this representation and from kolmogorov complexity certain statements become evident.

(1) For any other representation of graphs, there exists a constant c such that the conditional kolgomorov complexity on this representation saves at most c bits from the kolmogorov complexity from adjacency matrix.

(2) Sparse graphs are highly compressible (adjacency matrix of sparse graph contain a lot of zeroes versus very few ones)

(3) Program p1(n) := find the nth graph g such that no graph preceding (in my representation) is isomorphic,. 
Program p2(n) := find the smallest graph that is isomorphic to the graph n.
program p3(n) := find the n' such that p1(n') = p2(n)
p3 is the function that compresses a graph

Each graph can be uniquelly represented as an adjacency matrix. This is simply an nxn matrix of values 0,1. Each graph can therefore be expressed uniquely as a string of length n^2 by sequentially concatenating each line. Graphs with cycles and directed graphs are also uniquely represented.

Examples:
The complete graph of degree 3 can be expressed as 011-101-110 -> 011101110
The graph with Nodes {1,2,3} and edges {{1, 2},{1,3}} can be expressed as 011-100-100 -> 011100100

From this representation and from kolmogorov complexity certain statements become evident.

(1) For any other representation of graphs, there exists a constant c such that the conditional kolgomorov complexity on this representation saves at most c bits from the kolmogorov complexity from adjacency matrix.

(2) Sparse graphs are highly compressible (adjacency matrix of sparse graph contain a lot of zeroes versus very few ones)

I hope this answers your question.

@Qiaochu Yuan by statement (1), your representation will only save a bounded number of bits.

Each graph can be uniquelly represented as an adjacency matrix. This is simply an nxn matrix of values 0,1. Each graph can therefore be expressed uniquely as a string of length n^2 by sequentially concatenating each line. Graphs with cycles and directed graphs are also uniquely represented.

Examples:
The complete graph of degree 3 can be expressed as 011-101-110 -> 011101110
The graph with Nodes {1,2,3} and edges {{1, 2},{1,3}} can be expressed as 011-100-100 -> 011100100

From this representation and from kolmogorov complexity certain statements become evident.

(1) For any other representation of graphs, there exists a constant c such that the conditional kolgomorov complexity on this representation saves at most c bits from the kolmogorov complexity from adjacency matrix.

(2) Sparse graphs are highly compressible (adjacency matrix of sparse graph contain a lot of zeroes versus very few ones)

I hope this answers your question.

@Qiaochu Yuan My statements are concerned with kolmogorov complexity. In the case of graph isomorphism, we are only concerned with the matrices such that no permutation of lines can result in a smaller number. My statements are valid since they are all within the context of kolmogorov complexity.