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
. .
.