graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, the lexicographic product or (graph) composition of graphs and is a graph such that * the vertex set of is the

cartesian product In mathematics, specifically set theory, the Cartesian product of two sets and , denoted , is the set of all ordered pairs where is an element of and is an element of . In terms of set-builder notation, that is A\times B = \. A table c ...

; and * any two vertices and are adjacent in if and only if either is adjacent to in or and is adjacent to in . If the edge relations of the two graphs are

order relation Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article intro ...

s, then the edge relation of their lexicographic product is the corresponding

lexicographic order In mathematics, the lexicographic or lexicographical order (also known as lexical order, or dictionary order) is a generalization of the alphabetical order of the dictionaries to sequences of ordered symbols or, more generally, of elements of a ...

. 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 In mathematics, the distributive property of binary operations is a generalization of the distributive law, which asserts that the equality x \cdot (y + z) = x \cdot y + x \cdot z is always true in elementary algebra. For example, in elementary ...

with respect to disjoint union: . In addition it satisfies an identity with respect to complementation: . In particular, the lexicographic product of two

self-complementary graph In the mathematical field of graph theory, a self-complementary graph is a graph which is isomorphic to its complement. The simplest non-trivial self-complementary graphs are the path graph and the cycle graph. There is no known characteri ...

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

Notes

References

*. *. * * *.

External links

*{{mathworld , title = Graph Lexicographic Product , urlname = GraphLexicographicProduct Graph products