Lexicographic product of graphs

File:Graph-lexicographic-product.svg

The lexicographic product of graphs.

In graph theory, the lexicographic product or (graph) composition Template:Math of graphs Template:Mvar and Template:Mvar is a graph such that

• the vertex set of Template:Math is the cartesian product Template:Math; and
• any two vertices Template:Math and Template:Math are adjacent in Template:Math if and only if either Template:Mvar is adjacent to Template:Mvar in Template:Mvar or Template:Math and Template:Mvar is adjacent to Template:Mvar in Template:Mvar.

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 Template:Harvs.Template:Sfnp As Template:Harvtxt showed, the problem of recognizing whether a graph is a lexicographic product is equivalent in complexity to the graph isomorphism problem.Template:Sfnp

Properties

The lexicographic product is in general noncommutative: Template:Math. However it satisfies a distributive law with respect to disjoint union: Template:Math. In addition it satisfies an identity with respect to complementation: Template:Math. 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:Template:Sfnp

Template:Math.

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

Template:Math.

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:

Template:Math, where Template:Math.

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

References

• .
• .
• .