Extendability of the Complementary Prism of Extendable Graphs
Pongthep Janseana, Nawarat Ananchuen · Thai Journal of Mathematics · 2015
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$. Let $\overline{G}$ denote the complement of a simple graph $G$. The complementary prism of $G$ denoted by $G\overline{G}$ can be obtained by taking a copy of $G$ and a copy of $\overline{G}$ and then joining corresponding vertices by an edge. In this paper, we show that for positive integers $l_1$ and $l_2$, there exists a non-bipartite graph $G$ such that $G$ is $l_1$-extendable and $\overline{G}$ is $l_2$-extendable. Further, we show that if $G$ is $l_1$-extendable and $\overline{G}$ is $l_2$-extendable non-bipartite graphs for $l_1 \geq 2$ and $l_2 \geq 2$, then $G\overline{G}$ is $(l+1)$-extendable where $l = min\{l_1, l_2\}$. Finally, we provide an example of graph $G\overline{G}$ such that $G\overline{G}$ is not 2-extendable when both $G$ and $\overline{G}$ are 1-extendable non-bipartite. \vskip0.3cm oindent {\bf Keywords :} matching; extendable; complement; complementary prism.