Q : ¿El gráfico bipartito completo $K_{12,12}$ se descomponen en $K_{4,4}-I$ subgráficos, donde $I$ es un $1$ -(es decir, un la combinación perfecta )?
Las condiciones necesarias obvias funcionan:
-
$K_{12,12}$ tiene $12^2$ aristas que es divisible por $12$ el número de aristas en $K_{4,4}-I$ .
-
Vértices en $K_{12,12}$ tener un título $12$ que es divisible por $3$ el grado de los vértices en $K_{4,4}-I$ .
No me he esforzado demasiado en resolver esto hasta ahora. Parece que requeriría un esfuerzo considerable para resolverlo computacionalmente, así que espero que haya una solución más inteligente.
Una forma alternativa de pensar en este problema:
Q : ¿Existe un $12 \times 12$ matriz que contiene $12$ copias de cada símbolo en $\{1,2,\ldots,12\}$ de manera que cada fila y cada columna que contenga una copia del símbolo $i$ contiene exactamente $3$ copias de $i$ ?
Esta pregunta es un caso concreto de otro problema en el que estoy pensando.
