Strongly regular tournament

978 Views Asked by At

A digraph on $n$ vertices is called a tournament if there is a exactly one directed edge between any two distinct vertices. A vertex $v$ dominates a vertex $w$ if there is an edge from $v$ to $w$.

Let $dm(v)$ be the set of vertices that are dominated by $v$, and $dm(v,w)$ be the set of vertices that are dominated by both $v$ and $w$. Then the digraph is called a regular tournament if there is a positive integer $m$ such that $dm(v)=m$ for all $v$, and strongly regular if there are positive integers $m_1$ and $m_2$ such that $dm(v,w)=m_1$ for all $v \neq w$ and $dm(v)=m_2$ for all $v$.

I am asked to show that if a tournament is regular that $n$ is odd and that if it is strongly regular that $4 \mid n-3$. I am allowed to use the fact that in a regular digraph, for every vertex $v$ the in-degree of $v$ is equal to the out-degree of $v$.

The first part is not too hard: if $G$ is a tournament and we remove a vertex $v$ from $G$ then the in-degree of $v$ is equal to the out-degree so $G/v$ must have an even number of vertices.

I have not been able to solve the second part of the question.

1

There are 1 best solutions below

0
On

Late answer, but it might be useful to someone.

The sum of the out-degrees of all vertices is $n(n-1)/2$ (since a tournament on $n$ vertices has exactly $n(n-1)/2$ edges), so $m_2 = (n-1)/2$.

Now let $A$ be the set of couples of distinct edges directed to a same vertex.

$A = \{(u,w),(v,w) \in E^2, u \neq v\}$

For one vertex $u$, we can consider the set of the couples of edges that come from two different $v$ and $w$ to $u$. As the in-degree of $v$ is $m_2$ (since, as you said, for each vertex $v$, the in-degree is equal to the out-degree), this set has $m_2(m_2 - 1)/2$ elements.

Taking all those sets for every vertex in our graph gives a partition of $A$, thus $A$ has $n\cdot m_2(m_2 - 1)/2$ elements.

An other partition of $A$ is given by the sets $dm(v,w)$ you defined for every couple of vertices. So the number of elements of $A$ is equal to $n(n-1)/2 \cdot m_1$.

We conclude that $n\cdot m_2(m_2 - 1)/2 = n(n-1)/2 \cdot m_1$ which gives $n = 4m_1 + 3$.