2
$\begingroup$

Give an example of 2 non isomorphic regular tournament of the same order

I tried so many tournaments of the same order but got no luck, if they are regular, meaning all vertices of them have the same in and out degree, so they have arc preserved, which end up to make them isomorphic. I'm not sure there are such tournaments exist.

$\endgroup$

1 Answer 1

2
$\begingroup$

According to the data at http://cs.anu.edu.au/~bdm/data/digraphs.html, there is only one isomorphism class of semi-regular tournaments on five vertices, but there are five classes on six vertices and three on seven. (The tournaments themselves are there, the three on seven are regular.)

[This is a corrected answer, as indicated by Brian M. Scott.]

$\endgroup$
8
  • 1
    $\begingroup$ The tournaments on $6$ vertices aren’t regular: they’re only semi-regular. However, the same data show $3$ non-isomorphic regular tournaments on $7$ vertices; that will be the smallest example. $\endgroup$ Nov 10, 2014 at 0:00
  • $\begingroup$ I'm not sure I understand these matrices, can you explain it a little bit further for me please? the matrices I think it only show like 2-3 rows, the remaining rows are all zero? $\endgroup$ Nov 10, 2014 at 0:01
  • 2
    $\begingroup$ @XiaoXiaoZhen: The top line, $111000101101101011101$, for $7$ vertices, expands into the part of an adjacency matrix above the diagonal. If the vertices are labelled $1,\ldots,7$, a $1$ in row $i$, column $j$ indicates an edge $i\to j$, and a $0$ indicates an edge $i\leftarrow j$. Here’s the matrix: $$\pmatrix{-&1&1&1&0&0&0\\ -&-&1&0&1&1&0\\ -&-&-&1&1&0&1\\ -&-&-&-&0&1&1\\ -&-&-&-&-&1&0\\ -&-&-&-&-&-&1 }$$ Each of the other two lines expands similarly, and each of the three resulting matrices gives you a tournament on $7$ vertices. $\endgroup$ Nov 10, 2014 at 0:08
  • $\begingroup$ @BrianM.Scott So they are non-isomorphic because their matrices are not the same? I draw the picture out and spend almost all night but still can't see why they are non-isomorphic $\endgroup$ Nov 10, 2014 at 12:08
  • $\begingroup$ @XiaoXiaoZhen: The fact that the matrices are different isn’t enough to show that the graphs are not isomorphic, since the vertices could be permuted. I’ve not tried to verify that the graphs are non-isomorphic, so I really don’t know how hard it is to do so; it could conceivably be something that’s easiest to do on a computer, actually checking the possible maps to show that none is an isomorphism. $\endgroup$ Nov 10, 2014 at 12:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .