路Pn的補(bǔ)圖Pn的可擴(kuò)性研究

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

路Pn的補(bǔ)圖Pn的可擴(kuò)性研究

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

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

路 補(bǔ)圖 完美匹配 可擴(kuò)性

一、引言

筆者僅討論有限、無(wú)向、簡(jiǎn)單圖，所使用的記號(hào)和術(shù)語(yǔ)約定如下。其中未說(shuō)明的部分請(qǐng)參考文獻(xiàn)。

二、主要結(jié)果

為了證明方便，我們對(duì)路Pn的補(bǔ)圖的頂點(diǎn)集邊集

（如下圖）。

首先我們考慮偶長(zhǎng)路P2n的補(bǔ)圖的可擴(kuò)性。

定理1.偶長(zhǎng)路P2n的補(bǔ)圖的1-可擴(kuò)的。

情形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）的完美匹配。

綜上可得偶長(zhǎng)路P2n的補(bǔ)圖的1-可擴(kuò)的。

接下來(lái)我們考慮奇長(zhǎng)路P2n+1的補(bǔ)圖的可擴(kuò)性。

定理2.奇長(zhǎng)路P2n+1的補(bǔ)圖是-可擴(kuò)的。

情形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)用（第二版）.中國(guó)科學(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.

（責(zé)編 齊 真）