Lexicographic product of graphs

File:Graph-lexicographic-product.svg

The lexicographic product of graphs.

In graph theory, the lexicographic product or (graph) composition G ∙ H of graphs G and H is a graph such that

• the vertex set of G ∙ H is the cartesian product V(G) × V(H); and
• any two vertices (u,v) and (x,y) are adjacent in G ∙ H if and only if either u is adjacent to x in G or u = x and v is adjacent to y in H.

If the edge relations of the two graphs are order relations, then the edge relation of their lexicographic product is the corresponding lexicographic order.

It is one of 4 common graph products including Cartesian, tensor, and strong.

The lexicographic product was first studied by Felix Hausdorff (1914). As Feigenbaum & Schäffer (1986) 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: G ∙ H ≠ H ∙ G. However it satisfies a distributive law with respect to disjoint union: (A + B) ∙ C = A ∙ C + B ∙ C. In addition it satisfies an identity with respect to complementation: C(G ∙ H) = C(G) ∙ C(H). 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:

α(G ∙ H) = α(G)α(H).

The clique number of a lexicographic product is as well multiplicative:

ω(G ∙ H) = ω(G)ω(H).

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:

χ(G ∙ H) = χ_b(G), where b = χ(H).

The lexicographic product of two graphs is a perfect graph if and only if both factors are perfect.

References

• .
• .
• .