30 votos

¿Cuántos nodos en el grafo kk-denso más pequeño?

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+112k+11. ¿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.

6voto

tyson blader Puntos 18

Teorema. Un grafo kk-denso tiene al menos 2k+112k+11 vértices.

Prueba. Sea LL una copia del conjunto de vértices VV, con elementos lvlv para vVvV. Sea MM el grafo bipartito en el conjunto de vértices VLVL, con aristas wlvwlv siempre que w=vw=v o ww sea un hijo de vv. La condición kk-densa implica que para cualquier LL con |L|k, el conjunto de vecinos Γ(L)={vV(lwL).vlwE(M)} tiene un orden de al menos 2|L|+1. Esto implica que M no tiene ningún ciclo C de longitud 2k o menos: tomar L=CL daría |L|k y |Γ(L)|2|L|. Así que M tiene una circunferencia de al menos 2(k+1), y ambas partes de M tienen un grado promedio de 3. El límite de Hoory [1] (prueba alternativa en [2]) da |V|1+2+4++2k=2k+11.

Observación. Sospecho, pero no he comprobado, que el límite de Hoory solo es exacto para grafos regulares. El teorema de Feit-Higman dice que los únicos grafos regulares que alcanzan el límite anterior tienen una circunferencia de 5,6,8 o 12, lo que significa que solo podría haber grafos k-densos de orden 2k+11 para k=2,3,5 (y k=1). Creo que se puede construir un grafo k-denso a partir de una jaula (3,2k+2) (por ejemplo, la jaula Tutte 12) quite fácilmente tomándola como "M" y usando un emparejamiento perfecto para elegir qué vértices en L deben etiquetarse como lv.

[1] Tamaño de Grafos Bipartitos con una Circunferencia Dada, Shlomo Hoory, https://www.sciencedirect.com/science/article/pii/S0095895602921234

[2] Una prueba basada en la entropía del límite de Moore para grafos irregulares, S. Ajesh Babu, Jaikumar Radhakrishnan, https://arxiv.org/abs/1011.1058

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X