Lexicographic product of graphs
In graph theory, the lexicographic product or (graph) composition   of graphs  and  is a graph such that
 the vertex set of  is the cartesian product ; and
 any two vertices  and  are adjacent in  if and only if either  is adjacent with  in  or  and  is adjacent with  in . If the edge relations of the two graphs are order relations, then the edge relation of their lexicographic product is the corresponding lexicographic order. The lexicographic product was first studied by . As  showed, the problem of recognizing whether a graph is a lexicographic product is equivalent in complexity to the graph isomorphism problem. Properties
The lexicographic product is in general noncommutative: . However it satisfies a distributive law with respect to disjoint union: . In addition it satisfies an identity with respect to complementation: . In particular, the lexicographic product of two self-complementary graphs is self-complementary. The independence number of a lexicographic product may be easily calculated from that of its factors :
. The clique number of a lexicographic product is as well multiplicative:
. The chromatic number of a lexicographic product is equal to the b-fold chromatic number of G, for b equal to the chromatic number of H:
, where . The lexicographic product of two graphs is a perfect graph if and only if both factors are perfect . References
. . . External links 

Graph products