On matching extendability of lexicographic products.


N. Chiarelli, C. Dibek, T. Ekim, D. Gozupek, and S. Miklavic, “On matching extendability of lexicographic products.” RAIRO - Oper. Res. vol. 51, no. 3, pp. 857-873, 2017.
Download Here549 KB


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.

Last updated on 01/03/2020