基本極大（m+1）K-,2--free圖.pdf

1、G的匹配M是導(dǎo)出匹配如果[4]E(V(M))=M。圖G的導(dǎo)出匹配數(shù)IM(G)，表示圖G的一個(gè)最大導(dǎo)出匹配的邊數(shù)。是否存在一個(gè)連通不完全簡單圖G，對其中每一對不相鄰的頂點(diǎn)x和y，都有IM(G+xy)=IM(G)+1?這是一個(gè)有趣而且基本的問題。 本文研究了極大2K<,2>-free圖的一些特征，并構(gòu)造了一些頂點(diǎn)數(shù)是12，13，14的極大2K<,2>-free圖。H是圖G的一個(gè)正則導(dǎo)出子圖，如果H是圖G的一個(gè)導(dǎo)出子圖，而且H≠G。我

2、們稱G是一個(gè)極大(m+1)K<,2>-free圖，如果G是一個(gè)連通非完全簡單圖，使得任意給定一對非相鄰的頂點(diǎn)x和y，IM(G+xy)=IM(G)+1=m+1。那么是否存在三正則極大(m+1)K<,2>-free圖呢?這個(gè)問題仍然是一個(gè)open problem。我們說G是一個(gè)基本極大(m+1)K<,2>-free圖，如果G是一個(gè)極大(m+1)K<,2>-free圖，而且圖G的任何一個(gè)正則導(dǎo)出子圖都不是一個(gè)極大(n+1)K<,2>-free