# Graph Invariants (covering design)

Technically 2 graphs are NOT isomorphic if any one of the countless graph invariants (i.e. vertices, edges, etc…) are not the same for both graphs.

I would like to know in this case which graph invariant is different between Graph A and Graph B for this covering design (v=10, k=6, t=3) which proves that Graph A and Graph B are NOT isomorphic. Furthermore, how is it calculated?

Graph A

1, 2, 3, 4, 6, 7

1, 2, 3, 5, 7, 10

1, 2, 3, 8, 9, 10

1, 2, 4, 6, 8, 10

1, 3, 4, 5, 6, 9

1, 4, 5, 7, 8, 9

2, 4, 5, 6, 9, 10

2, 5, 6, 7, 8, 9

3, 4, 5, 7, 8, 10

3, 6, 7, 8, 9, 10

Graph B

1, 2, 3, 4, 6, 7

1, 2, 3, 5, 8, 10

1, 2, 3, 7, 9, 10

1, 2, 4, 6, 8, 10

1, 3, 4, 5, 6, 9

1, 4, 5, 7, 8, 9

2, 4, 5, 6, 9, 10

2, 5, 6, 7, 8, 9

3, 4, 5, 7, 8, 10

3, 6, 7, 8, 9, 10

The only difference between Graph A and Graph B is in blocks 2 & 3 where the 7 and the 8 are inverted. All the other blocks are the same.

Thanks Roy

-
Okay... still trying to figure out what these numbers mean. Does each row of numbers represent the vertices adjacent to that particular vertex. (i.e. the 2nd row shows all the vertices adjacent to vertex 2 in $G$)? – Nicolas Villanueva May 26 '11 at 17:20
I also don't understand what the numbers mean. Can you use a more standard notation, such as an adjacency list (en.wikipedia.org/wiki/Adjacency_list) or adjacency matrix (en.wikipedia.org/wiki/Adjacency_matrix) or incidence matrix (en.wikipedia.org/wiki/Incidence_matrix)? – Qiaochu Yuan May 26 '11 at 17:45
Yes, presumably your book and/or class has defined a standard way of representing a "covering design" as a graph. If you could define that representation, it would help. Is it just the bipartite graph with $1..10$ in one set, and the cover sets in the other, with the an edge between number $n$ and cover set $S$ if $n\in S$? – Thomas Andrews May 26 '11 at 18:35
The website ccrwest.org/cover.html seems to define covering designs using this terminology, but now I don't see how one gives rise to a graph. – MartianInvader May 26 '11 at 20:52

In graph-theoretic terms covering designs $(v,k,t)$ represent a specific form of this more general case:
Select a graph $G=(V_1,E_1)$ and a second graph $H=(V_2,E_2)$ with $|V_1| \geq |V_2|$ and $|E_1| \geq |E_2|$. Then the task is to select subgraph(s) $g_i$ of $G$ isomorphic to $H$ such that a set of these subgraphs $(g_1,g_2,...g_n)$ covers some predefined features of $G$ ie. all edges, $n$-cycles, or $n$-cliques.
Usually the specific case refernced by the OP with $(v,k,t)$ given corresponds to this specific instance:
$G=K_v$, select a set of $k$-cliques in $G$ that covers every combination of $t$ nodes in $G$ at least once. Most frequently the problem is analyzed with $t=2$ which gives a set of $k$-cliques in $K_v$ that covers each edge of $K_v$. In the OP's case he has provide two sets of $6$-cliques, which, taken over an arbitrary labeling of the vertices of $K_{10}$ from $(1,2,...10)$, cover all $2$-paths ($3$-cycles) in $K_{10}$.