Extendability of the Complementary Prism of Extendable Graphs: Pongthep Janseana, Nawarat Ananchuen

Authors

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\noindent {\bf Keywords :} matching;

extendable; complement; complementary prism.