Grafo universal

En teoría de grafos, un grafo universal es un grafo infinito que contiene a todos los grafos finitos (o al menos numerables) como un subgrafo inducido. El primer grafo universal fue construido por R. Rado,[1][2] actualmente llamado grafo de Rado o grafo aleatorio.

Trabajos más recientes[3][4] se han enfocado en grafos universales para una familia de grafos particular F, correspondiente a aquella que contiene a todos los grafos finitos. Un grafo universal para una familia F de grafos también puede referirse a un miembro de una secuencia de grafos finitos que contiene a todos los grafos en F. Por ejemplo, cada árbol finito es un subgrafo de un grafo hipercubo suficientemente largo;[5] por lo tanto, un hipercubo puede decirse que es un grafo universal para los árboles.

En terminología matemática más antigua, la frase "grafo universal" fue a veces utilizada para denotar a los grafos completos.

Referencias
  1. Rado, R. (1964). «Universal graphs and universal functions». Acta Arithmetica (en inglés) 9: 331-340.
  2. Radio, R. (1967). «Universal graphs». A Seminar in Graph TheoryHolt, Reinhart, y Winston: 83-85.
  3. Goldstern, Martin; Kojman, Menachem (1996). «Universal arrow-free graphs». Acta Math. Hungar (en inglés) 1973: 319-326. doi:10.1007/BF00052907. arΧiv:math.LO/9409206.
  4. Cherlin, Greg; Shelah, Saharon; Shi, Niandong (1999). «Universal graphs with forbidden subgraphs and algebraic closure». Advances in Applied Math (en inglés) 22: 454-491. doi:10.1006/aama.1998.0641. arΧiv:math.LO/9809202.
  5. Wu, A. Y (1985). «Embedding of tree networks into hypercubes». Journal of Parallel and Distributed Computing (en inglés) 2: 238-249. doi:10.1016/0743-7315(85)90026-7.
Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.