Árbol Xuong

Un árbol Xuong. Solo un componente de los bordes que no son del árbol (el componente rojo) tiene un número impar de bordes, el mínimo posible para este gráfico.

En teoría de grafos , un árbol Xuong es un árbol de expansión de un grafo dado con la propiedad de que, en el grafo restante , el número de componentes conectados con un número impar de aristas es lo más pequeño posible. ^[1] Se denominan así en honor a Nguyen Huy Xuong, quien los utilizó para caracterizar las incrustaciones celulares de un grafo dado que tiene el género más grande posible . ^[2] ${\displaystyle T}$ ${\displaystyle G}$ ${\displaystyle G-T}$

Según los resultados de Xuong, si es un árbol Xuong y el número de aristas en los componentes de es , entonces el género máximo de una incrustación de es . ^{[1] [2]} Cualquiera de estos componentes, que tenga aristas, se puede dividir en caminos de dos aristas disjuntos en aristas, con posiblemente una arista restante adicional. ^[3] Una incrustación de género máximo se puede obtener a partir de una incrustación plana del árbol Xuong agregando cada camino de dos aristas a la incrustación de tal manera que aumente el género en uno. ^{[1] [2]} ${\displaystyle T}$ ${\displaystyle G-T}$ ${\displaystyle m_{1},m_{2},\dots ,m_{k}}$ ${\displaystyle G}$ ${\displaystyle \textstyle \sum _{i=1}^{k}\lfloor m_{i}/2\rfloor }$ ${\displaystyle m_{i}}$ ${\displaystyle \lfloor m_{i}/2\rfloor }$

Se puede encontrar un árbol Xuong y una incrustación de género máximo derivada de él en cualquier gráfico en tiempo polinomial , mediante una transformación a un problema computacional más general sobre matroides , el problema de paridad de matroides para matroides lineales . ^{[1] [4]}

Referencias

1. Beineke, Lowell W. ; Wilson, Robin J. (2009), Temas de teoría de grafos topológicos , Enciclopedia de matemáticas y sus aplicaciones, vol. 128, Cambridge University Press, Cambridge, pág. 36, doi :10.1017/CBO9781139087223, ISBN 978-0-521-80230-7, Sr.  2581536
2. Xuong, Nguyen Huy (1979), "Cómo determinar el género máximo de un grafo", Journal of Combinatorial Theory , Serie B, 26 (2): 217–225, doi : 10.1016/0095-8956(79)90058-3 , MR  0532589
3. Sumner, David P. (1974), "Gráficos con 1-factores", Actas de la American Mathematical Society , 42 (1), American Mathematical Society: 8–12, doi :10.2307/2039666, JSTOR  2039666, MR  0323648
4. Furst, Merrick L.; Gross, Jonathan L.; McGeoch, Lyle A. (1988), "Encontrar una incrustación de grafos de género máximo", Journal of the ACM , 35 (3): 523–534, doi : 10.1145/44483.44485 , MR  0963159, S2CID  17991210