4
$\begingroup$

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.

$\endgroup$
8
  • 3
    $\begingroup$ 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?). $\endgroup$ Mar 7, 2014 at 3:01
  • $\begingroup$ @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. $\endgroup$ Mar 9, 2014 at 9:47
  • $\begingroup$ What is the value of $\gamma$ for a projective plane of order $q$? $\endgroup$ Mar 9, 2014 at 14:22
  • $\begingroup$ 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. $\endgroup$ Mar 9, 2014 at 21:01
  • 1
    $\begingroup$ @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)"... $\endgroup$ Mar 9, 2014 at 21:24

2 Answers 2

7
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$ Mar 9, 2014 at 16:33
2
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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). $\endgroup$ Mar 9, 2014 at 11:22
  • $\begingroup$ I think I lost you in the extra comment. :( $\endgroup$ Mar 9, 2014 at 11:39
  • $\begingroup$ 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 $\endgroup$ Mar 9, 2014 at 11:42
  • $\begingroup$ 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)$. $\endgroup$ Mar 9, 2014 at 11:49
  • 1
    $\begingroup$ GAP package Design can apparently produce such a list for you, see gap-system.org/Manuals/pkg/design/htm/CHAP007.htm $\endgroup$ Mar 9, 2014 at 14:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.