Lexicographic product of graphs

From Wikipedia, the free encyclopedia

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) $\times$ V(H); and
any two vertices (u,u') and (v,v') are adjacent in G ∙ H if and only if either u is adjacent with v, or u = v and u' is adjacent with v' .

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 and Schäffer (1986) showed, the problem of recognizing whether a graph is a lexicographic product is equivalent in complexity to the graph isomorphism problem.

1 Properties
2 Application
3 References
4 External links

[edit] 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).

The independence number of a lexicographic product may be easily calculated from that of its factors:

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

(Geller and Stahl 1975).

The chromatic number of a lexigraphic product is as well multiplicative:

$\omega(G\cdot H) = \omega(G)\cdot \omega(H)$

[edit] Application

In 1972 Abbott gave a curios super-quadratic constructive lower bound for the Ramsey numbers: Suppose you have a n-vertex graph G with independence number and clique number smaller than n¹⁰ (or any other power) The same relations hold for the graph G ∙ G or any larger powers of G. This gives a infinite sequence of explicit Ramsey graphs provided that we have the graph to start from. By checking all the graphs on k^10 vertices (k large enough), one of them certainly will be k-Ramsey.

[edit] References

Feigenbaum, J.; Schäffer, A. A. (1986). "Recognizing composite graphs is equivalent to testing graph isomorphism". SIAM J. Comput. 15: 619–627. doi:10.1137/0215045. MR 0837609.

Geller, D.; Stahl, S. (1975). "The chromatic number and other functions of the lexicographic product". Journal of Combinatorial Theory, Series B 19: 87–95. doi:10.1016/0095-8956(75)90076-3. MR 0392645.