3
$\begingroup$

If $G$ is a digraph with $n$ vertices (self-loops are allowed) such that every vertex has the out-degree equal to $k$ and every pair of distinct vertices has exactly $m$ common neighbors ($y$ is considered a neighbor of $x$ if there is an arc from $x$ to $y$), is it true that $G$ is strongly regular?

Can we prove that also the in-degree of every vertex is $k$ and that every two distinct vertices are common neighbors of exactly $m$ vertices?

I assume that, probably, there must be some connection between $n$, $k$ and $m$ such that this is true.

$\endgroup$

1 Answer 1

2
$\begingroup$

It's certainly not universally true. Consider the graph $G$ with vertex set $\{1,2,\dots,n\}$ and an edge $i \to 1, i \to 2, \dots, i \to k$ for all $i$. (Some of these are loops)

Then any vertex has out-degree $k$, and any two vertices have $k$ common neighbors, but some vertices have in-degree $0$ while other vertices have in-degree $n$. Of course, here, we're limited to $k=m$.

On the other hand, $m=1$ is a case where we can deduce lots of structure; in particular, that all in-degrees are equal to $k$ and any two vertices have exactly one in-neighbor.

Define an incidence structure with $n$ points $P_1, \dots, P_n$ and $n$ lines $L_1, \dots, L_n$ where point $P_i$ lies on line $L_j$ exactly when the graph has an edge $i \to j$. Then the out-degree condition says that there are exactly $k$ lines through each point, and the common-neighbor condition says that through any two points, there is exactly one line. A theorem of de Bruijn and Erdős says that all incidence structures with this property and with more than one line (the one-line case is the trivial $k=m$ example mentioned earlier) also satisfy:

  • $n = k^2-k+1$,
  • all lines contain exactly $k$ points.

(Finite projective planes are an example of incidence structures with this property, but not the only example.)

The condition that all lines contain exactly $k$ points means that all in-degrees are also equal to $k$.

Each of the $k$ points on a line $L$ lies on $k-1$ other lines, and since no line intersects $L$ twice, we get $k(k-1)$ distinct lines that intersect $L$. Since there are $k^2-k+1 = k(k-1)+1$ lines total, this includes all the lines other than $L$, so $L$ intersects every other line at exactly one point. This means that any two vertices in the graph have exactly one common in-neighbor.


In general, if we prove the first part of your claim - that all in-degrees are equal to $k$ - then the second part of your claim automatically follows. In this case, the in-neighborhoods of the vertices form a block design: all blocks have size $k$, any point is contained in $k$ blocks, and any pair of distinct points is contained in $m$ blocks.

This is a symmetric block design: the number of points is equal to the number of blocks. In a symmetric block design, any two blocks must overlap in $m$ exactly points. One proof of this is found here.

$\endgroup$

You must log in to answer this question.

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