Un torneo es un grafo dirigido tal que para cada par de los distintos vértices $\{x,y\}$, hay un borde de $x$ a $y$ o de $y$ a $x$, pero no tanto. Voy a utilizar "$x\to y$" significa que "hay un borde de $x$ a $y$."
Un dominante conjunto de un grafo dirigido es un subconjunto $S$ de vértices tal que para cada a$t\notin S$existe $s\in S$ lo $s\to t$.
Puede demostrarse$^*$ que cada torneo en $2^{n+1}-2$ vértices tiene un dominador conjunto de tamaño $n$. Mi pregunta es si este resultado es apretado.
¿Existe un torneo en $2^{n+1}-1$ vértices sin dominando conjunto de tamaño $n$?
Si no, ¿cuál es el más pequeño torneo sin dominando conjunto de tamaño $n$?
Mis pensamientos:
Una condición necesaria para que una gráfica en la $2^{n+1}-1$ vértices sin dominando conjunto de tamaño $n$ es que cada vértice debe tener un grado de exactamente $2^n-1$, exactamente la mitad de sus bordes salientes.
La respuesta es sí cuando se $n=1,2$.
- La "piedra-papel-tijeras" gráfico en tres vértices no tiene dominando conjunto de tamaño $1$.
- En la gráfica de $\mathbb Z/7\mathbb Z$ donde cada una de las $x$ ha dirigido a los bordes de la $x+1,x+2$ e $x+4\pmod7$ no tiene dominando conjunto de tamaño $2$.
Para $n\ge 3$, las posibilidades de conseguir demasiado grande, y yo no puede venir para arriba con una solución inteligente. ¿Alguien puede ver un patrón?
Se me ocurrió este problema, mientras que el pensamiento acerca de este rompecabezas.
$^*$Considere la posibilidad de un vértice $s$ con la máxima fuera de grado. Por el hand-shaking lema, este grado debe ser de al menos $(2^{n+1}-3)/2$, así que al menos $2^n-1$. Incluir $s$ en $S$, luego ignorar $s$ y los vértices $t$ para que $s\to t$. Lo que queda del torneo de tamaño $(2^{n+1}-2)-1-(2^{n}-1)=2^n-2$. Proceder por inducción.
