En teoría de grafos , el producto lexicográfico o composición (gráfica) G ∙ H de los grafos G y H es un grafo tal que
Si las relaciones de arista de los dos gráficos son relaciones de orden , entonces la relación de arista 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 un grafo es un producto lexicográfico es equivalente en complejidad al problema del isomorfismo de grafos .
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 disjunta: ( 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 grafos 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):
El número de camarilla de un producto lexicográfico es también multiplicativo:
El número cromático de un producto lexicográfico es igual al número cromático b -vez de G , siendo b igual al número cromático de H :
El producto lexicográfico de dos gráficos es un gráfico perfecto si y sólo si ambos factores son perfectos (Ravindra y Parthasarathy 1977).
{{citation}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace )