Volume 33 • Number 2 • 2010   • Lexicographic Product of Extendable Graphs Bing Bai, Zefang Wu, Xu Yang and Qinglin Yu Abstract. Lexicographic product G ο H of two graphs G and H has vertex set V(G) × V(H) and two vertices (u1, v1) and (u2, v2) are adjacent whenever u1u2 ∈ E(G), or u1 = u2 and v1u2 ∈ 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. 2000 Mathematics Subject Classification: 05C70, 05C76. Full text: PDF