Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

1 Answer 1

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.

share|improve this answer
    
Please contact me asap at my first.lastname@gmail.com –  Bill Dubuque Sep 6 '12 at 14:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.