Lexicographic Product of Extendable Graphs.

Lexicographic product G ∘ H of two graphs G and H has vertex set V (G) x V (H) and two vertices (u1; v1) and (u2; v2) are adjacent whenever u1u2 ∊ E(G), or u1 = u2 and v1v2 ∊ E(H). If every matching of G of size k can be extended to a perfect matching in G, then G is called k-extendable. In this paper, we study matching extendability in lexicographic product of graphs. The main result is that the lexicographic product of an m-extendable graph and an n-extendable graph is (m + 1)(n + 1)-extendable. In fact, we prove a slightly stronger result. [ABSTRACT FROM AUTHOR]