Lexicographic product of graphs
In graph theory, the lexicographic product or 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 to in or and is adjacent to in .
It is one of 4 common graph products including Cartesian, tensor, and strong.
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:
The lexicographic product of two graphs is a perfect graph if and only if both factors are perfect.