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

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.

• My guess is that the domination number will depend on the structure. If the design is resolvable, then you will need exactly $v/k$ blocks to dominate the points, while if it is not resolvable, you will need more. I can't see how this would alter the number of points needed to dominate the blocks (but perhaps it does?). – Gordon Royle Mar 7 '14 at 3:01
• @GordonRoyle On the other hand, if the dominating set is of the form $P \cup B$, then the points in $P$ do not have to be dominated by the blocks in $B$. So resolvability may have much of an effect on $\gamma$. But I'm going to think about this angle for sure. – Felix Goldberg Mar 9 '14 at 9:47
• What is the value of $\gamma$ for a projective plane of order $q$? – Dima Pasechnik Mar 9 '14 at 14:22
• Hmm, for $q=2$ this gives $\gamma=2$. This cannot be right, as the size of the set of neighbours of such a set is at most 6, but the graph has 14 vertices. – Dima Pasechnik Mar 9 '14 at 21:01
• @DimaPasechnik Oops, sorry, I meant $2q$. The $q$th order plane is a $(q^2+q+1,q+1,1)$-design and I meant "twice of (one less the degree of the design)"... – Felix Goldberg Mar 9 '14 at 21:24

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$.

• Yikes! These are probably 6 or 7 points and 4 or 3 blocks, right? I had worried if this kind of thing could happen after my "answer". I will edit to remove errors! – Peter Dukes Mar 9 '14 at 16:33

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.

• Attacking my own reasoning: it does seem plausible that, in each system, some 8-subset could generate all but three blocks. Anyway I think I have a "cheat" solution, based on the above. If we take 13 copies of $PG_3(2)$ on the same points, the domination number is still (at worst) 11 via a subspace plus four blocks. On the other hand, the complete design of all triples on 15 points has domination number 13, I believe. So the answer is negative for (15,3,13) designs (when repeated blocks are permitted). – Peter Dukes Mar 9 '14 at 11:22
• I think I lost you in the extra comment. :( – Felix Goldberg Mar 9 '14 at 11:39
• I am starting to consider Steiner systems so will try to check your argument on some examples. P.S. Is there a place where one can obtain all 80 systems in a machine format? I only have the 44 listed by Spence on his excellent webpage maths.gla.ac.uk/~es/bibd/15-3-1 – Felix Goldberg Mar 9 '14 at 11:42
• Sorry about the confusion. My added comment just says that if your search fails for $(15,3,1)$-designs, then you can get a counterexample for $(15,3,13)$-designs. On the one hand, 13 copies of the geometry results in domination number 11, while the complete design (all $\binom{15}{3}$ triples) has domination number $12+1 = 13$. If you don't like repeated blocks, or $\lambda=13$ is too high, I suspect you can apply the same sort of idea with $\lambda=3$ and permuting around the copies of $PG_3(2)$. – Peter Dukes Mar 9 '14 at 11:49
• GAP package Design can apparently produce such a list for you, see gap-system.org/Manuals/pkg/design/htm/CHAP007.htm – Dima Pasechnik Mar 9 '14 at 14:07