Consideremos un grafo dirigido kk-denso si:
- Cada nodo tiene exactamente dos hijos (vecinos salientes);
- Cada par de nodos tiene al menos tres hijos diferentes (además de ellos mismos);
- Cada tres nodos tienen al menos cuatro hijos diferentes (además de ellos mismos);
- ...
- Cada kk nodos tienen al menos k+1k+1 hijos diferentes (además de ellos mismos);
¿Cuál es el número más pequeño de nodos requerido para un grafo kk-denso?
Aquí hay algunos casos especiales.
Para k=1k=1, el número más pequeño de nodos es 33:
1->[2,3], 2->[3,1], 3->[1,2]
Para k=2k=2, el número más pequeño de nodos es 77. Para ver esto, podemos construir el grafo avariciosamente basándonos en la siguiente restricción: el hijo de un nodo debe ser diferente a su padre y hermano(s). ¿Por qué? Porque un nodo y su padre deben tener tres hijos además de ellos mismos.
- 11 tiene dos hijos: llámelos 22 y 33.
- 22 debe tener dos hijos diferentes a su padre (11) y hermano (33): llámelos 44 y 55.
- 33 debe tener dos hijos diferentes a su padre (11) y hermano (22). El primero puede ser 44. Ahora, 33 y 22 juntos solo tienen dos hijos además de ellos mismos (44 y 55), por lo que 33 debe tener otro hijo diferente - llámelo 66.
- 44 debe tener dos hijos diferentes a sus padres (22 y 33) y hermanos (55 y 66). El primero puede ser 11 y el segundo debe ser nuevo - llámelo 77.
- 55 debe tener dos hijos diferentes a su padre (22) y hermano (44). El primero puede ser 11. El segundo no puede ser uno de los hijos de 11 (22 y 33) o hermanos (77) por lo que debe ser 66.
- 66 debe tener dos hijos diferentes a sus padres (33 y 55) y hermanos (44 y 11). Estos deben ser 22 y 77.
- 77 debe tener dos hijos diferentes a sus padres (44 y 66) y hermanos (22 y 11). Estos deben ser 33 y 55.
En total, tenemos el siguiente grafo 22-denso con n=7n=7 nodos:
1->[2,3] 2->[4,5] 3->[4,6] 4->[1,7] 5->[1,6] 6->[2,7] 7->[3,5]
Para k=3k=3, usé un algoritmo avaricioso similar (con más restricciones) para construir el siguiente grafo:
1->[2,3] 2->[4,5] 3->[6,7] 4->[6,8] 5->[7,9]
6->[10,11] 7->[12,13] 8->[1,9] 9->[10,14] 10->[2,12]
11->[1,13] 12->[8,15] 13->[4,14] 14->[3,15] 15->[5,11]
Utilicé un programa de computadora para verificar todas las posibilidades con un máximo de 1414 nodos y no encontré ninguna, por lo que (asumiendo que mi programa es correcto) n=15n=15 es el número mínimo requerido para k=3k=3.
Esto sugiere que el número mínimo de nodos en un grafo kk-denso debería ser: 2k+1−12k+1−1. ¿Es esto cierto?
¿Cuál es el número más pequeño de nodos requerido para kk en general?
ACTUALIZACIÓN 1: Acabo de aprender sobre la expansión de vértices. Parece estar relacionado, pero aún no estoy seguro de cómo exactamente.