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
Rado, R. (1964). «Universal graphs and universal functions». Acta Arithmetica(en inglés)9: 331-340.
Radio, R. (1967). «Universal graphs». A Seminar in Graph TheoryHolt, Reinhart, y Winston: 83-85.
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.
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.
Datos:Q7894131
Agosto 17, 2021
grafo, universal, teoría, grafos, grafo, universal, grafo, infinito, contiene, todos, grafos, finitos, menos, numerables, como, subgrafo, inducido, primer, grafo, universal, construido, rado, actualmente, llamado, grafo, rado, grafo, aleatorio, trabajos, más, . En teoria 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 mas 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 tambien puede referirse a un miembro de una secuencia de grafos finitos que contiene a todos los grafos en F Por ejemplo cada arbol 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 arboles En terminologia matematica mas antigua la frase grafo universal fue a veces utilizada para denotar a los grafos completos Referencias Editar Rado R 1964 Universal graphs and universal functions Acta Arithmetica en ingles 9 331 340 Radio R 1967 Universal graphs A Seminar in Graph TheoryHolt Reinhart y Winston 83 85 Goldstern Martin Kojman Menachem 1996 Universal arrow free graphs Acta Math Hungar en ingles 1973 319 326 doi 10 1007 BF00052907 arXiv math LO 9409206 Cherlin Greg Shelah Saharon Shi Niandong 1999 Universal graphs with forbidden subgraphs and algebraic closure Advances in Applied Math en ingles 22 454 491 doi 10 1006 aama 1998 0641 arXiv math LO 9809202 Wu A Y 1985 Embedding of tree networks into hypercubes Journal of Parallel and Distributed Computing en ingles 2 238 249 doi 10 1016 0743 7315 85 90026 7 Datos Q7894131Obtenido de https es wikipedia org w index php title Grafo universal amp oldid 120213294, wikipedia, wiki, leyendo, leer, libro, biblioteca,
