Extendability of the Complementary Prism of 2-Regular Graphs

Pongthep Janseana, Sriphan Rueangthampisan, Nawarat Ananchuen

Abstract

Let $G$ be a simple graph. The complementary prism of $G$, denoted by $G\overline{G}$,

is the graph formed from the disjoint union of $G$ and $\overline{G}$,

the complement of $G$, by adding the edges of a perfect matching between the corresponding vertices of $G$ and $\overline{G}$. 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$. The problem that arises is that of investigating the extendability of $G\overline{G}$.

In this paper, we investigate the extendability of $G\overline{G}$ where $G$ contains $G_1, \ldots, G_l$ as its components and the extendability of $G_i\overline{G}_i$ is known for $1 \leq i \leq l$. We then apply this result to establish the extendability of $G\overline{G}$ when $G$ is 2-regular.