Lexicographic product of graphs

The lexicographic product of graphs.

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

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 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: GHHG. However it satisfies a distributive law with respect to disjoint union: (A + B) ∙ C = AC + BC. In addition it satisfies an identity with respect to complementation: C(GH) = C(G) ∙ C(H).

The independence number of a lexicographic product may be easily calculated from that of its factors (Geller & Stahl 1975):

α(GH) = α(G)α(H).

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

ω(GH) = ω(G)ω(H).

The lexicographic product of two graphs is a perfect graph if and only if both factors are perfect (Ravindra & Parthasarathy 1977).

References

External links

This article is issued from Wikipedia - version of the Monday, February 08, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.