ON MATCHING EXTENDABILITY OF LEXICOGRAPHIC PRODUCTS

Abstract

A graph G of even order is l-extendable if it is of order at least 2l + 2, contains a matching of size l, and if every such matching is contained in a perfect matching of G. In this paper, we study the extendability of lexicographic products of graphs. We characterize graphs G and H such that their lexicographic product is not 1-extendable. We also provide several conditions on the graphs G and H under which their lexicographic product is 2-extendable.