En teoría de grafos , el producto lexicográfico o composición (gráfica) G ∙ H de los gráficos G y H es un gráfico tal que
- el conjunto de vértices de G ∙ H es el producto cartesiano V (G) × V (H) ; y
- cualquiera de los dos vértices ( u , v ) y ( x , y ) son adyacentes en G ∙ H si y sólo si cualquiera de u es adyacente con x en G o u = x y v es adyacente con y en H .
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/6/64/Graph-lexicographic-product.svg/300px-Graph-lexicographic-product.svg.png)
Si las relaciones de los bordes de los dos gráficos son relaciones de orden , entonces la relación de los bordes de su producto lexicográfico es el orden lexicográfico correspondiente .
El producto lexicográfico fue estudiado por primera vez por Felix Hausdorff ( 1914 ). Como demostraron Feigenbaum y Schäffer (1986) , el problema de reconocer si una gráfica es un producto lexicográfico es equivalente en complejidad al problema del isomorfismo de la gráfica .
Propiedades
El producto lexicográfico es en general no conmutativo : G ∙ H ≠ H ∙ G . Sin embargo, satisface una ley distributiva con respecto a la unión de la desunión: ( A + B ) ∙ C = A ∙ C + B ∙ C . Además, satisface una identidad con respecto a la complementación : C ( G ∙ H ) = C ( G ) ∙ C ( H ) . En particular, el producto lexicográfico de dos gráficos autocomplementarios es autocomplementario.
El número de independencia de un producto lexicográfico se puede calcular fácilmente a partir del de sus factores ( Geller y Stahl 1975 ):
- α ( G ∙ H ) = α ( G ) α ( H ) .
El número de camarilla de un producto lexicográfico también es multiplicativo:
- ω ( G ∙ H ) = ω ( G ) ω ( H ) .
El número cromático de un producto lexicográfico es igual al número cromático b veces mayor de G , para b igual al número cromático de H :
- χ ( G ∙ H ) = χ b ( G ) , donde b = χ ( H ).
El producto lexicográfico de dos gráficos es un gráfico perfecto si y solo si ambos factores son perfectos ( Ravindra y Parthasarathy 1977 ).
Referencias
- Feigenbaum, J .; Schäffer, AA (1986), "El reconocimiento de gráficos compuestos es equivalente a probar el isomorfismo de los gráficos", SIAM Journal on Computing , 15 (2): 619–627, doi : 10.1137 / 0215045 , MR 0837609.
- Geller, D .; Stahl, S. (1975), "El número cromático y otras funciones del producto lexicográfico", Journal of Combinatorial Theory , Serie B, 19 : 87–95, doi : 10.1016 / 0095-8956 (75) 90076-3 , MR 0392645.
- Hausdorff, F. (1914), Grundzüge der Mengenlehre , Leipzig
- Imrich, Wilfried; Klavžar, Sandi (2000), Gráficos de productos: estructura y reconocimiento , Wiley, ISBN 0-471-37039-8
- Ravindra, G .; Parthasarathy, KR (1977), "Perfect product graphs", Discrete Mathematics , 20 (2): 177–186, doi : 10.1016 / 0012-365X (77) 90056-5 , hdl : 10338.dmlcz / 102469 , MR 0491304.