基本極大（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è)連通不完全簡(jiǎn)單圖G，對(duì)其中每一對(duì)不相鄰的頂點(diǎn)x和y，都有IM(G+xy)=IM(G)+1?這是一個(gè)有趣而且基本的問(wèn)題。 本文研究了極大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è)連通非完全簡(jiǎn)單圖，使得任意給定一對(duì)非相鄰的頂點(diǎn)x和y，IM(G+xy)=IM(G)+1=m+1。那么是否存在三正則極大(m+1)K<,2>-free圖呢?這個(gè)問(wèn)題仍然是一個(gè)open problem。我們說(shuō)G是一個(gè)基本極大(m+1)K<,2>-free圖，如果G是一個(gè)極大(m+1)K<,2>-free圖，而且圖G的任何一個(gè)正則導(dǎo)出子圖都不是一個(gè)極大(n+1)K<,2>-free