Title of article :
Lexicographic Product of Extendable Graphs
Author/Authors :
Bai, Bing Nankai University - Center for Combinatorics, LPMC, China , Wu, Zefang Nankai University - Center for Combinatorics, LPMC, China , Yang, Xu Nankai University - Center for Combinatorics, LPMC, China , Yu, Qinglin Thompson Rivers University - Department of Mathematics and Statistics, Canada
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 in E(G), or u1 = u2 and v1v2 in 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.
Keywords :
Lexicographic product , extendable graph , factor , criticality , perfect matching , T , join.
Journal title :
Bulletin of the Malaysian Mathematical Sciences Society
Journal title :
Bulletin of the Malaysian Mathematical Sciences Society
