Is the domination number of a combinatorial design determined by the design parameters?

Question

Let $D$ be a $(v,k,\lambda)$-design. By the domination number of $D$ I mean the domination number $\gamma(L(D))$ of the bipartite incidence graph of $D$.

Is $\gamma(L(D))$ determined only by $v,k$, and $\lambda$, irrespective of the actual structure of $D$?

I can prove this for finite projective planes and have empirically verified this property for $(8,4,3)$ and $(10,4,2)$-designs (of which there are four and three non-isomorphic ones, respectively).

P.S. Has the domination number of such graphs been studied at all? I could only find one paper by Laskar et al. which considered the line graphs of the incidence graphs.

Answer 1

Well, interestingly enough, all the 80 Steiner triple systems on 15 points have minimum dominating sets of size 10 - there is more tradeoff between the points/blocks than I first recognised.

But if we go a bit bigger then we can find some variation. Here is a $2$-$(25,4,1)$ design with 50 blocks.

0 1 2 3; 0 4 5 6; 0 7 8 9; 0 10 11 12; 0 13 14 15; 0 16 17 18; 0 19 20 21; 0 22 23 24; 1 4 7 10; 1 5 8 13; 1 6 14 16; 1 9 11 19; 1 12 15 22; 1 17 20 23; 1 18 21 24; 2 4 8 23; 2 5 7 21; 2 6 12 24; 2 9 10 17; 2 11 14 18; 2 13 20 22; 2 15 16 19; 3 4 13 18; 3 5 11 22; 3 6 7 19; 3 8 12 17; 3 9 15 24; 3 10 16 20; 3 14 21 23; 4 9 16 22; 4 11 20 24; 4 12 14 19; 4 15 17 21; 5 9 14 20; 5 10 15 18; 5 12 16 23; 5 17 19 24; 6 8 15 20; 6 9 18 23; 6 10 21 22; 6 11 13 17; 7 11 15 23; 7 12 18 20; 7 13 16 24; 7 14 17 22; 8 10 14 24; 8 11 16 21; 8 18 19 22; 9 12 13 21; 10 13 19 23;

and here is another

0 1 2 3; 0 4 5 6; 0 7 8 9; 0 10 11 12; 0 13 14 15; 0 16 17 18; 0 19 20 21; 0 22 23 24; 1 4 7 10; 1 5 8 13; 1 6 16 19; 1 9 14 22; 1 11 20 23; 1 12 17 21; 1 15 18 24; 2 4 11 18; 2 5 7 24; 2 6 8 21; 2 9 16 20; 2 10 15 19; 2 12 13 22; 2 14 17 23; 3 4 12 23; 3 5 15 20; 3 6 7 17; 3 8 10 22; 3 9 11 19; 3 13 18 21; 3 14 16 24; 4 8 14 20; 4 9 15 17; 4 13 19 24; 4 16 21 22; 5 9 12 18; 5 10 16 23; 5 11 14 21; 5 17 19 22; 6 9 13 23; 6 10 14 18; 6 11 15 22; 6 12 20 24; 7 11 13 16; 7 12 14 19; 7 15 21 23; 7 18 20 22; 8 11 17 24; 8 12 15 16; 8 18 19 23; 9 10 21 24; 10 13 17 20;

My computer tells me that the first one has a dominating set of size 13, namely the $9$ points $$\{1,2,7,12,14,17,18,20,22\}$$ and the four blocks $$\{0,4,5,6 \mid 3, 9 ,15, 24 \mid 8 ,11, 16 ,21 \mid 10, 13, 19, 23\}.$$ You can check this by hand and probably also convince yourself that no fewer than $13$ will do.

However the computer also tells me that the second design has no dominating set of size $13$, but how you would convince yourself of this by hand is another matter.

P.S While I was at it, I tried the $960$ $2$-$(10,3,2)$ designs (which have 30 blocks so are a bit smaller) and determined that $42$ have domination number $6$, and the remainder $7$.

Answer 2

Gordon has done a proper search of $(15,3,1)$-designs. I guess my incorrect reasoning does lead to a computer-free proof for (15,3,13)-designs. This is kind of cheating though, because there are repeated blocks if one takes 13 copies of a STS. The idea may work for smaller $\lambda$; see my own comment below.

Following up on Gordon's comment, consider the projective Steiner triple system $PG_3(2)$ on 15 points. Concretely, the points can be presented as the nonzero binary 4-tuples; blocks are the triples of vectors with zero sum.

Now, the points are dominated by a parallel class of 5 blocks: $$ \begin{array}{ccc} 0001 &0010 &0011\\ 0100 &1000 &1100\\ 0101 &1010 &1111\\ 0110 &1101 &1011\\ 0111 &1001 &1110\\ \end{array} $$ The blocks are dominated by a maximal subspace of 7 points (e.g. those quadruples with a leading zero).

What's more, one block of the above parallel class can be taken inside the subspace. So I think we get domination number $\le 11=(5-1)+7$. It is going to be hard (see below) to do this well in general. (Here I was very wrong!)

It is easy to see that, in a Steiner triple system of order $v$, covering all points with $v/3$ blocks is best possible and can occur if and only if there is a parallel class. Likewise, touching all blocks with $(v-1)/2$ points is best possible and occurs if and only if they form a flat. (A quick counting argument is needed.)

This is the key issue it turns out: I acknowledge it is not correct for me to separately consider points and blocks in your bipartite graph. That is, I have not checked carefully whether not having to dominate the chosen points by blocks, and vice-versa, fails to help enough for one of these "bad" systems.