Poder de las hojas

Un árbol (arriba) y su correspondiente poder de 3 hojas (abajo)

En el área matemática de la teoría de grafos , una potencia de k hojas de un árbol es un gráfico cuyos vértices son las hojas de y cuyos bordes conectan pares de hojas cuya distancia en es como máximo . Es decir, es un subgrafo inducido de la potencia del gráfico , inducido por las hojas de . Para un gráfico construido de esta manera, se llama raíz de k -leaf .${\displaystyle T}$${\displaystyle G}$${\displaystyle T}$${\displaystyle T}$${\displaystyle k}$${\displaystyle G}$ ${\displaystyle T^{k}}$${\displaystyle T}$${\displaystyle G}$${\displaystyle T}$${\displaystyle G}$

Un gráfico es una potencia de hoja si es una potencia de hoja para algunos . ^[1] Estos gráficos tienen aplicaciones en filogenia , el problema de reconstruir árboles evolutivos.${\displaystyle k}$${\displaystyle k}$

Clases de gráficos relacionados

Dado que las potencias de los gráficos fuertemente cordales son fuertemente cordales y los árboles son fuertemente cordales, se deduce que las potencias de las hojas son fuertemente cordales. ^[2] En realidad, los poderes de las hojas forman una subclase adecuada de grafos fuertemente cordales; un gráfico es una potencia de hoja si y solo si es un gráfico NeST de tolerancia fija ^[3] y tales gráficos son una subclase adecuada de gráficos fuertemente cordales. ^[4]

En Brandstädt et al. (2010) se muestra que los gráficos de intervalo y la clase más grande de gráficos de trayectoria dirigida con raíces son poderes de hoja. Los gráficos de indiferencia son exactamente los poderes de las hojas cuyos árboles subyacentes son orugas .

Las k potencias de las hojas para los valores acotados de k tienen un ancho de camarilla acotado , pero esto no es cierto para las potencias de las hojas con exponentes ilimitados. ^[5]

Estructura y reconocimiento

Problema no resuelto en informática :

¿Existe un algoritmo de tiempo polinómico para el reconocimiento de los poderes de la hoja o poderes para -leaf ?${\displaystyle k}$${\displaystyle k\geq 7}$

(más problemas sin resolver en informática)

Un gráfico es un poder de 2 hojas si y solo si es la unión disjunta de camarillas (es decir, un gráfico de conglomerados ). ^[1]

Una gráfica es una potencia de 3 hojas si y solo si es una gráfica de cuerdas libre de (toro, dardo, gema) . ^[6] Con base en esta caracterización y otras similares, las potencias de 3 hojas se pueden reconocer en tiempo lineal . ^[7]

Las caracterizaciones de las potencias de 4 hojas las dan Rautenbach (2006) y Brandstädt, Le & Sritharan (2008) , que también permiten el reconocimiento de tiempo lineal. El reconocimiento de los gráficos de potencia de 5 hojas y 6 hojas también se resuelve en tiempo lineal por Chang y Ko (2007) ^[8] y Ducoffe (2018), ^[9] respectivamente.

Para ≥ 7, el problema de reconocimiento de las potencias de las hojas está abierto, e igualmente, es un problema abierto si las potencias de las hojas se pueden reconocer en el tiempo polinomial . Sin embargo, se ha demostrado que el reconocimiento de potencias de hoja es manejable con parámetros fijos cuando se parametriza por y la degeneración del gráfico de entrada. ^[10]${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$

Notas

1. Nishimura, Ragde y Thilikos (2002) .
2. Dahlhaus y Duchet (1987) ; Lubiw (1987) ; Raychaudhuri (1992) .
3. Brandstädt y col. (2010) ; Hayward, Kearney y Malton (2002) .
4. Broin y Lowe (1986) ; Bibelnieks y Dearing (1993) .
5. Brandstädt y Hundt (2008) ; Gurski y Wanke (2009) .
6. Dom y col. (2006) ; Rautenbach (2006)
7. Brandstädt y Le (2006) .
8. Ko, Ming-Tat; Chang, Maw-Shang (21 de junio de 2007). El problema de la raíz de 3 Steiner . Conceptos teóricos de grafos en informática . Apuntes de conferencias en Ciencias de la Computación. Springer, Berlín, Heidelberg. págs. 109-120. doi : 10.1007 / 978-3-540-74839-7_11 . ISBN 9783540748380.
9. Ducoffe, Guillaume (4 de octubre de 2018). "Reconocimiento de tiempo polinomial de 4 poderes Steiner". arXiv : 1810.02304 [ cs.CC ].
10. Eppstein, David; Havvaei, Elham (1 de agosto de 2020). "Reconocimiento de poder de hoja parametrizado mediante la incrustación en productos gráficos" . Algoritmica . 82 (8): 2337–2359. doi : 10.1007 / s00453-020-00720-8 . ISSN 1432-0541 . S2CID 218988055 .  

Referencias

• Bibelnieks, E .; Dearing, PM (1993), "Gráficos de tolerancia de subárboles de vecindario", Matemáticas aplicadas discretas , 43 : 13–26, doi : 10.1016 / 0166-218X (93) 90165-K.
• Brandstädt, Andreas; Hundt, Christian (2008), "Las gráficas ptolemaicas y las gráficas de intervalo son poderes foliares", LATIN 2008: Informática teórica , Lecture Notes in Comput. Sci., 4957 , Springer, Berlín, págs. 479–491, doi : 10.1007 / 978-3-540-78773-0_42 , ISBN 978-3-540-78772-3, MR  2472761.
• Brandstädt, Andreas ; Hundt, Christian; Mancini, Federico; Wagner, Peter (2010), "Los gráficos de trayectoria dirigidos con raíces son poderes de hoja", Matemáticas discretas , 310 (4): 897–910, doi : 10.1016 / j.disc.2009.10.006.
• Brandstädt, Andreas ; Le, Van Bang (2006), "Estructura y reconocimiento de tiempo lineal de poderes de 3 hojas", Information Processing Letters , 98 (4): 133-138, CiteSeerX  10.1.1.144.3486 , doi : 10.1016 / j.ipl.2006.01 .004.
• Brandstädt, Andreas ; Le, Van Bang; Sritharan, R. (2008), "Estructura y reconocimiento de tiempo lineal de potencias de 4 hojas", ACM Transactions on Algorithms , 5 : 1–22, doi : 10.1145 / 1435375.1435386 , S2CID  6114466.
• Brandstädt, Andreas ; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey , SIAM Monographs on Discrete Mathematics and Applications, ISBN 978-0-89871-432-6.
• Broin, MW; Lowe, TJ (1986), "Gráficos de tolerancia de subárboles de vecindad", SIAM J. Algebr. Métodos discretos , 7 : 348–357, doi : 10.1137 / 0607039.
• Dahlhaus, E .; Duchet, P. (1987), "Sobre grafos fuertemente cordales", Ars Combinatoria , 24 B : 23-30.
• Dahlhaus, E .; Manuel, PD; Miller, M. (1998), "Una caracterización de grafos fuertemente cordales", Matemáticas discretas , 187 (1-3): 269-271, doi : 10.1016 / S0012-365X (97) 00268-9.
• Dom, M .; Guo, J .; Hüffner, F .; Niedermeier, R. (2006), "Compensación de errores en problemas de raíces de hojas", Algorithmica , 44 (4): 363–381, CiteSeerX  10.1.1.218.490 , doi : 10.1007 / s00453-005-1180-z , S2CID  75279.
• Farber, M. (1983), "Caracterizaciones de grafos fuertemente cordales", Matemáticas discretas , 43 (2-3): 173-189, doi : 10.1016 / 0012-365X (83) 90154-1.
• Gurski, Frank; Wanke, Egon (2009), "El ancho NLC y el ancho de la camarilla para potencias de gráficos de ancho de árbol acotado", Discrete Applied Mathematics , 157 (4): 583–595, doi : 10.1016 / j.dam.2008.08. 031 , MR  2499471.
• Hayward, RB; Kearney, PE; Malton, A. (2002), "Gráficos NeST", Matemáticas aplicadas discretas , 121 (1-3): 139-153, doi : 10.1016 / s0166-218x (01) 00207-4.
• Lubiw, A. (1987), "Doble ordenación léxica de matrices", SIAM Journal on Computing , 16 (5): 854–879, doi : 10.1137 / 0216057.
• McKee, TA (1999), "Una nueva caracterización de grafos fuertemente cordales", Matemáticas discretas , 205 (1–3): 245–247, doi : 10.1016 / S0012-365X (99) 00107-7.
• Nishimura, N .; Ragde, P .; Thilikos, DM (2002), "Sobre potencias gráficas para árboles etiquetados con hojas", Journal of Algorithms , 42 : 69–108, CiteSeerX  10.1.1.43.1127 , doi : 10.1006 / jagm.2001.1195.
• Rautenbach, D. (2006), "Algunas observaciones sobre las raíces de las hojas", Matemáticas discretas , 306 (13): 1456–1461, doi : 10.1016 / j.disc.2006.03.030.
• Raychaudhuri, A. (1992), "Sobre potencias de grafos fuertemente cordales y grafos de arco circular", Ars Combinatoria , 34 : 147-160.
• Eppstein, D .; Havvaei, H. (2020), "Reconocimiento de poder de hoja parametrizado mediante incrustación en productos gráficos" , Algorithmica , 82 (8): 2337–2359, doi : 10.1007 / s00453-020-00720-8 , S2CID  218988055.