Extendability of the Complementary Prism of 2-Regular Graphs

Pongthep Janseana, Sriphan Rueangthampisan, Nawarat Ananchuen


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.

Full Text: PDF


  • There are currently no refbacks.

The Thai Journal of Mathematics organized and supported by The Mathematical Association of Thailand and Thailand Research Council and the Center for Promotion of Mathematical Research of Thailand (CEPMART).

Copyright 2020 by the Mathematical Association of Thailand.

All rights reserve. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, without the prior permission of the Mathematical Association of Thailand.

|ISSN 1686-0209|