1
$\begingroup$

I am not a mathematician so please take that into consideration when formulating your answers. 

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

  • 0
    The website http://www.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.2011-05-26

1 Answers 1

2

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}$.

This notation still does not provide a definitive answer to the original question because there are many ways the individual sets of blocks could be combined into a "graph", but hopefully it provides some motivation for the notation and the question.

  • 0
    Please contact me asap at my first.lastname@gmail.com2012-09-06