王錦偉 （ 蘭州工業(yè)學(xué)院基礎(chǔ)學(xué)科部 730050）

路Pn的補圖Pn的可擴性研究

王錦偉 （ 蘭州工業(yè)學(xué)院基礎(chǔ)學(xué)科部 730050）

在連通圖中任取n條點不交的邊，如果這些邊可以擴充成的一個完美匹配，就稱連通圖是n-可擴的。本文中我們主要研究偶長路P2n的補圖的1-可擴性以及奇長路 的補圖的-可擴性。

路 補圖 完美匹配 可擴性

一、引言

筆者僅討論有限、無向、簡單圖，所使用的記號和術(shù)語約定如下。其中未說明的部分請參考文獻。

二、主要結(jié)果

為了證明方便，我們對路Pn的補圖的頂點集邊集

（如下圖）。

首先我們考慮偶長路P2n的補圖的可擴性。

定理1.偶長路P2n的補圖的1-可擴的。

情形1.k和k的奇偶性相同。

不妨假設(shè)k和k都是奇數(shù)且有k＜i。于是C=ij（ j+2）...（2n-1） 13...（i-2）（i+2）...（j-2） 24...（2n）是的一條Hamilton路，因此存在包含（）,i j的完美匹配。

情形2.k和k的奇偶性不同。

不妨假設(shè)k是奇數(shù)，k是偶數(shù)且k＜i，于是C=ij（ j+2）...（2n）24...（i-1）（i+1）...（j-2） 13...（i-2）（i+2）...(2n -1)是的一條Hamilton路，因此存在包含（i, j）的完美匹配。

綜上可得偶長路P2n的補圖的1-可擴的。

接下來我們考慮奇長路P2n+1的補圖的可擴性。

定理2.奇長路P2n+1的補圖是-可擴的。

情形1.,,i j k的奇偶性相同。

情形2.k和k的奇偶性相同，與k的奇偶性不同。

情形3.k和k的奇偶性不同。

不妨假設(shè)k是奇數(shù)，k是偶數(shù)且有ki＜。而k與k或k的奇偶性相同，不妨假設(shè)k是偶數(shù)。

[1]徐俊明.圖論及其應(yīng)用（第二版）.中國科學(xué)技術(shù)大學(xué)出版社，2005.

[2]M.D.Plummer， On n-extendable graphs，Discrete Math. 31（1980）201-210.

[3]Q.Yu，Characterizations of various matching extensions in gaphs，Australas. J.Combin.7（1993） 55-64.

（責編 齊 真）