On matching extendability of lexicographic products
Nina Chiarelli, Cemil Dibek, Tınaz Ekim, Didem Gözüpek, Štefko Miklavič · RAIRO - Operations Research · 2016
A graph G of even order is ℓ-extendable if it is of order at least 2ℓ + 2, contains a matching of size ℓ, 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.