MATCHING EXTENSION IN COMPLEMENTARY PRISM OF REGULAR GRAPHS

Abstract

Let \(\overline{G}\) denote the complement of a simple graph \(G\).  The complementary prism of \(G\), denoted by \(G\overline{G}\), is obtained by taking a copy of \(G\) and a copy of \(\overline{G}\) and then adding a perfect matching that joins corresponding vertices.  A connected graph \(G\) of order at least 2k + 2 is k-extendable if for every matching M of size k in \(G\), there is a perfect matching in \(G\) containing all edges of M .  In this paper, we establish some sufficient conditions for the complementary prism of regular graphs to be 2-extendable.