stringtranslate.com

Árbol K

El gráfico de Goldner-Harary , un ejemplo de un árbol de 3 ejes planar.

En teoría de grafos , un árbol k es un grafo no dirigido que se forma comenzando con un grafo completo de ( k  + 1) vértices y luego agregando vértices repetidamente de tal manera que cada vértice agregado v tiene exactamente k vecinos U tales que, juntos, los k  + 1 vértices formados por v y U forman una camarilla . [1] [2]

Caracterizaciones

Los k -árboles son exactamente los grafos máximos con un ancho de árbol de k ("máximo" significa que no se pueden agregar más aristas sin aumentar su ancho de árbol). [2] También son exactamente los grafos cordales cuyas camarillas máximas tienen el mismo tamaño k  + 1 y cuyos separadores de camarillas mínimos también tienen el mismo tamaño k . [1]

Clases de gráficos relacionadas

Los árboles 1 son lo mismo que los árboles . Los árboles 2 son grafos serie-paralelos maximalistas , [3] e incluyen también los grafos maximalistas exteriores-planares . Los árboles 3 planares también se conocen como redes apolíneas . [4]

Los grafos que tienen un ancho de árbol como máximo k son exactamente los subgrafos de k -árboles, y por esta razón se denominan k -árboles parciales . [2]

Los gráficos formados por los bordes y vértices de politopos apilados de dimensión k , politopos formados a partir de un símplex y luego pegando repetidamente símplex sobre las caras del politopo, son árboles k cuando k  ≥ 3. [5] Este proceso de pegado imita la construcción de árboles k al agregar vértices a una camarilla. [6] Un árbol k es el gráfico de un politopo apilado si y solo si ninguna camarilla de tres ( k  + 1) vértices tiene k vértices en común. [7]

Referencias

  1. ^ ab Patil, HP (1986), "Sobre la estructura de los árboles k ", Journal of Combinatorics, Information and System Sciences , 11 (2–4): 57–64, MR  0966069.
  2. ^ abc Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2008), "Propiedades estructurales de grafos dispersos" (PDF) , en Grötschel, Martin ; Katona, Gyula OH (eds.), Construyendo puentes: entre las matemáticas y la informática , Bolyai Society Mathematical Studies, vol. 19, Springer-Verlag, p. 390, ISBN 978-3-540-85218-6.
  3. ^ Hwang, Frank; Richards, Dana ; Winter, Pawel (1992), El problema del árbol de Steiner , Anales de matemáticas discretas (Estudios de matemáticas de Holanda Septentrional), vol. 53, Elsevier, pág. 177, ISBN 978-0-444-89098-6.
  4. ^ Distancias en estructuras de redes apolíneas aleatorias Archivado el 21 de julio de 2011 en Wayback Machine , diapositivas de la charla de Olivier Bodini, Alexis Darrasse y Michèle Soria de una charla en FPSAC 2008, consultado el 6 de marzo de 2011.
  5. ^ Koch, Etan; Perles, Micha A. (1976), "Eficiencia de cobertura de árboles y árboles k ", Actas de la Séptima Conferencia del Sureste sobre Combinatoria, Teoría de Grafos y Computación (Universidad Estatal de Luisiana, Baton Rouge, La., 1976) , Utilitas Math., Winnipeg, Man., págs. 391–420. Congressus Numerantium, N.º XVII, MR  0457265. Véase en particular la pág. 420.
  6. ^ Abajo, Alexander; De Loera, Jesús A.; Richter-Gebert, Jürgen (febrero de 2004), "La complejidad de encontrar pequeñas triangulaciones de 3-politopos convexos", Journal of Algorithms , 50 (2): 134–167, arXiv : math/0012177 , doi :10.1016/s0196-6774(03)00092-0
  7. ^ Kleinschmidt, Peter (1 de diciembre de 1976), "Eine graphentheoretische Kennzeichnung der Stapelpolytope", Archiv der Mathematik , 27 (1): 663–667, doi :10.1007/BF01224736