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
    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$)?2011-05-26
  • 0
    I also don't understand what the numbers mean. Can you use a more standard notation, such as an adjacency list (http://en.wikipedia.org/wiki/Adjacency_list) or adjacency matrix (http://en.wikipedia.org/wiki/Adjacency_matrix) or incidence matrix (http://en.wikipedia.org/wiki/Incidence_matrix)?2011-05-26
  • 0
    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$?2011-05-26
  • 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