全變換圖Gxyz?

李亞平，吳寶音都仍

(新疆大學 數(shù)學與系統(tǒng)科學學院, 新疆 烏魯木齊, 830046)

0 引言

設G=(V(G),E(G)) 是一個簡單無向圖. 對沒有說明的術(shù)語和概念可參考[1, 2]. 圖G的一個點v, 在G中的度記為dG(v),v的鄰點記為NG(v) 是{u∈V(G)|uv∈E(G)}. 兩個點u和v之間的距離dG(u,v)是它們之間最短路的長度.

我們用符號?(G),δ(G),κ(G),λ(G),α(G),α′(G) 和ω(G) 分別表示G的最大度, 最小度, 連通性, 邊連通性,獨立數(shù), 匹配數(shù)和團數(shù). 圖G的連通性(邊連通性)記為κ(G)(λ(G)), 被定義為使G是k?連通的(k?邊連通的)最大整數(shù)k. ?′(G)=max{dG(u)+dG(v)|uv∈E(G)}.

圖G的補圖, 記為, 它的點集與G的相同, 且其兩個點相鄰當且僅當它們在G中不相鄰. 圖G的線圖, 記為L(G), 它的頂點為E(G), 兩個點相鄰當且僅當在G中它們作為邊是相鄰的. 圖G的全圖T(G) 的點集是V(G)∪E(G), 且兩個點相鄰當且僅當它們在G中相鄰或關聯(lián).

設G=(V(G),E(G)) 是一個圖, 且α,β是V(G)∪E(G)的兩個元素. 如果α和β在G中是相鄰的或關聯(lián)的,我們就說它們的關系是+. 設xyz是集合+,?的3-置換. 如果α和β都在V(G)中(分別地,α和β都在E(G) 中或α和β中的一個在V(G)另一個在E(G)中), 我們就說α和β對應于xyz的第一項x(分別地, 第二項y或第三項z).

圖G的變換圖Gxyz定義在點集V(G)∪E(G)上,Gxyz的兩個點α和β是由一條邊相鄰的當且僅當它們在G中的關系和xyz的對應項相一致.因為有+,?的8個不同的3-置換,我們得到了8個圖G的變換圖. 有趣的是G+++恰好是G的全圖T(G), 且G???是T(G)的補圖. 又對給定的圖G,G++?和G??+,G+?+和G?+?,G?++和G+??是其它的3對互補圖.

變換圖Gxyz作為全圖的變換是由吳和孟[1]在2001年首次引進的，所有這些變換圖都具有很多好的性質(zhì).

1 基本性質(zhì)

若uv是G中的一條邊, 則我們用euv記為Gxyz中的點. 吳和孟[1]給出了Gxyz是連通的充分必要條件, 對每個xyz, 他們證明了Gxyz有好的連通性質(zhì).

定理1(吳和孟[1]) 對給定的圖G,G+++連通當且僅當G是連通的.

定理2(吳和孟[1]) 對給定的圖G,G++?連通當且僅當G至少有兩條邊, 且G2K2.

定理3(吳和孟[1]) 對給定的圖G,G+?+連通當且僅當G沒有孤立點.

定理4(吳和孟[1]) 對一個圖G,G+??連通當且僅當G至少有兩條邊.

定理5(吳和孟[1]) 對任何圖G,G?++是連通的.

定理6(吳和孟[1]) 對一個圖G,G?+?連通當且僅當G不是星圖.

定理7(吳和孟[1]) 對任何圖G,G??+是連通的.

定理8(吳和孟[1]) 對一個圖G,G???連通當且僅當G既不是星圖也不是三角形.

2 直徑

有趣的是，對一個圖G, 除了當xyz=+++ 時的情況, 如果Gxyz是連通的, 則它的直徑不大（不超過4）.

定理9(吳和孟[1]) 若G連通, 則

定理10(吳和孟[1]) 若G至少有兩條邊, 且G2K2, 則

等號成立當且僅當G2K2mK1,m>0.

定理11(吳和孟[1]) 若G沒有孤立點, 則

等號成立當且僅當G同構(gòu)于兩個星圖的不交并.

定理12(吳和孟[1]) 若G至少有兩條邊, 則

等號成立當且僅當GP3.

定理13(吳和孟[1]) 設G是一個圖, 則

等號成立當且僅當diam(L(G))>2.

定理14(吳和孟[1]) 若G不是星圖, 則diam(G?+?)≤3.

定理15(吳和孟[1]) 對任何圖G,diam(G??+)≤3, 等號成立當且僅當G包含一個三角形, 且圖G有一個度為2的點.

定理16(吳和孟[1]) 若G既不是星圖也不是三角形, 則diam(G???)≤3.

3 正則性

很明顯G是正則的當且僅當是正則的. 林和束[3]對Gxyz是正則的給出了充分必要條件.

定理17(林和束[3]) 若G是簡單圖, 則G+++和G???是正則的當且僅當G是正則的.

定理18(林和束[3])設G是一個n≥3 階的連通圖,G++?和G??+是正則的當且僅當GCn或K2,n?2或K4.

定理19(林和束[3]) 設G是一個n≥2 階圖, 且邊數(shù)為m,G+?+和G?+?是正則的當且僅當G=C5或K2或K7或K3,3或C3□K2.

定理20(林和束[3])設G是一個n階圖,且邊數(shù)為m≥1,G?++和G+??是正則的當且僅當G是正則圖.

4 平面性

在平面上畫一個圖時, 如果它的邊只相交在端點, 則稱這樣的圖為可嵌入平面的, 或可平面的. 圖的這種畫法叫做圖的平面嵌入. 著名的Kuratowski’s 定理[4]說一個圖是可平面的, 當且僅當它不含K5或K3,3的剖分圖.

下面所有的定理都可從Kuratowski’s 定理推導出. 若兩個圖G和H滿足V(G)∩V(H)=?, 則它們的不交并記為G+H.

定理21(Behzad[5]) 圖G的全圖G+++是平面的當且僅當?(G)≤3 且每個度為3的點是一個割點.

定理22(袁和劉[6]) 給定一個圖G,G++?是平面的當且僅當|E(G)|≤2 或G∈{C3,C3+K1,P4,P4+K1,P3+K2,P3+K2+K1,K1,3,K1,3+K1,3K2+K1,3K2+2K1,C4,C4+K1}.

定理23(王和劉[7]) 設G是邊數(shù)為m的圖, 則G+??是平面的當且僅當m≤2 或G同構(gòu)于下列圖中的一個:C3,C3+K1,P4,P4+K1,P3+K2,P3+K2+K1,K1,3,K1,3+K1,3K2,3K2+K1,3K2+2K1,C4,C4+K1,2P3.

定理24(吳, 張, 張[8]) 給定一個圖G,G?++是平面的當且僅當|V(G)|≤4.

定理25(王[9]) 給定一個圖G,G?+?是平面的當且僅當n≤4 且G不同構(gòu)于K4?e.

定理26(王[9]) 給定一個圖G,G??+是平面的當且僅當n≤3 或G同構(gòu)于下列圖中的一個: 2K1+K2,K1+K1,2,K1,3,K1+C3.

定理27(劉[10]) 設G是階數(shù)為n的圖, 則G???是平面的當且僅當n≤3 或G同構(gòu)于下列圖中的一個:2K2,C4,K4?e,K4,2K+K3,K1,4,K1+K1,3,2K1+P3.

現(xiàn)在只有當xyz=+?+ 的情況還沒有解決.

5 同構(gòu)

Gr¨unbaum[11]對任何圖的變換構(gòu)造了如下兩類基本問題: (1)確定性問題. 確定哪些圖有一個給定的圖作為它們的Gxyz；(2)刻畫性問題. 刻畫那些圖, 它是某個圖的變換圖Gxyz.

定理28(吳和孟[1]) 給定一個圖G,

(i)G+yz=G當且僅當G是一個空圖;

(ii)G?yz=G當且僅當G=K1.

定理29(吳, 張, 張[8]) 給定兩個圖G和G′,G?++=G′?++當且僅當G=G′.

定理30(吳, 張, 張[8]) 給定兩個圖G和G′,G+??=G′+??當且僅當G=G′.

猜想1(吳, 張, 張[8]) 給定兩個圖G和G′,G++?=G′++?當且僅當G=G′.

猜想2(吳, 張, 張[8]) 給定兩個圖G和G′,G+?+=G′+?+當且僅當G=G′.

有關Gxyz刻畫問題未被解決.

6 哈密頓性, 連通性和獨立數(shù)

6.1 哈密頓性

設G是一個圖. 如果一個圈包含圖G的所有頂點, 則這個圈稱為G的哈密頓圈. 一個圖若包含哈密頓圈, 則稱這個圖是哈密頓圖. 由Chv′atal 和Erd?os[12]的定理, 我們知道階至少是3的圖G, 如果滿足κ(G)≥α(G), 則G是哈密頓的.

EPS-子圖是由Fleischner 在文獻[13]中首次引入的, 圖G的EPS-子圖是一個連通的支撐子圖S,S是圖E和森林P的邊不交并,E(不一定連通)的所有頂點的度數(shù)都是偶度, 森林P(可能為空)的每一個分支是一條路.

定理31(Fleischner和Hobbs[14]) 設G是至少有兩個點的有限圖, 則G的全圖G+++是哈密頓的當且僅當G包含一個EPS-子圖.

以下關于Gxyz的哈密頓性的大部分定理都是從上面Chv′atal-Erd?os定理推導出來的.

定理32(馬和吳[15]) 設G是一個圖. 則G???是哈密頓的當且僅當G不同構(gòu)于以下的任何圖{K1,r|r≥1}∪{K1,s+K1|s≥1}∪{K1,t+e|t≥2}∪{K2+2K1,K3+K1,K3+2K1,K4}.

定理33(吳, 張, 張[8]) 若G是階數(shù)為n的圖,G?++是哈密頓的當且僅當n≥3.

定理34(徐和吳[16])若G是階數(shù)為n≥4的圖,G?+?是哈密頓的當且僅當G不同構(gòu)于以下的任何圖{K1,n?1,K1,n?1+e,K1,n?2+K1}{2K1+K2,K1+K3}.

定理 35(甄和吳[17]) 若G是沒有孤立點的圖,G+??是哈密頓的當且僅當G既不是星圖, 也不是G∈{2K2,K3,K1,1}.

定理36(伊和吳[18]) 設G是階為n≥6的圖, 且邊數(shù)為m. 若m≥α(G)+1, 則G++?是哈密頓的.

推論1(伊和吳[18]) 設G是階為n≥6的圖, 且邊數(shù)為m. 若m≥n, 則G++?是哈密頓的.

6.2 連通性

定理37(Sim?oes-pereira[19])

上述下界可進一步改進.

定理38(Hamada和Nonaka和Yoshimura[20])

定理39(Bauer 和Tindell[21]) 若λ(G)≥2, 則λ(G+++)=δ(G+++)=2δ(G).

定理40(張和黃[22]) 給定一個圖G,κ(G+?+)=δ(G+?+) 當且僅當下面三個條件都不滿足:

(1)G至少有兩個分支, 其中一個是K2, 且δ(G)≥1;

(2)G至少有兩個分支, 其中一個是K3, 且δ(G)≥2;

(3)G=K1,n.

推論2(張和黃[22]) 若G2K2, 則λ(G+?+)=δ(G+?+).

定理41(徐和吳[16])設G是階為n的圖,且邊數(shù)為m,則或min{δ(G?+?),n+κ(L(G)),m+κ(G)}.

定理42(伊和吳[18]) 設G是階為n≥6的圖, 且邊數(shù)為m≥3, 則κ(G++?)≥min{m?1,n+κ(L(G))?1}.

推論3(徐和吳[16]) 設G是階為n≥4的圖, 則以下情形等價:

(1)κ(G?+?)≥2;

(2)δ(G?+?)≥2;

(3)G/∈{K1,n?1,K1,n?1+e,K1,n?2+K1}.

推論4(徐和吳[16]) 設G是階為n≥4的圖,κ(G?+?)=2 當且僅當δ(G?+?)=2.

定理43(甄和吳[17]) 設G是階為p的圖, 且邊數(shù)為q,

6.3 獨立數(shù)

引理1(馬和吳[15]) 對一個給定的圖G, 如果?(G)=1則α(G???)=3, 否則α(G???)=?(G)+1.

定理44(馬和吳[15]) 對任何圖G,

等號成立當且僅當G包含一個三角形, 且?(G)=2.

定理45(徐和吳[16]) 對任何圖G,

定理46(吳, 張, 張[8]) 對任何圖G,λ(G?++)=δ(G?++).

定理47(甄和吳[17]) 對任何圖G,

定理48(伊和吳[18]) 對任何圖G,

7 超邊連通性和圈邊連通性

7.1 超邊連通性

若圖G滿足λ(G)=δ(G), 則稱它為極大邊連通的, 或簡稱G是max-λ. 如果對圖G的每個最小邊割T,G?T有孤立點, 則稱它為超邊連通的, 或簡稱G是super-λ.

定理49(陳和孟[23]) 若G是連通圖, 則G+++是super-λ當且僅當下面兩個條件之一成立:

(1)λ(G)≥2, 若G有一個割點x, 且dG(x)=δ(G), 則在x和G?x的任何分支之間存在3條或更多邊;

(2)λ(G)=1, 若e=xy是一個橋, 則min{dG(x),dG(y)}≥2δ(G).

定理50(陳和孟[23]) 設G是沒有孤立點的連通圖,G+?+是super-λ當且僅當G沒有孤立邊且GK1,n.

定理51(陳和孟[23]) 給定圖G,G?++是super-λ當且僅當GK1,n或K1,n∪K1.

推論5(陳和孟[23]) 對任何圖G,λ(G?++)=δ(G?++).

定理52(陳和孟[24]) 對任何圖G,G??+是max-λ并且G??+是super-λ當且僅當G既不同構(gòu)于K1,2也不同構(gòu)于K2∪K1.

推論6(陳和孟[24]) 對任何圖G,λ(G??+)=δ(G??+).

定理53(陳和孟[25]) 若G是至少有兩條邊的圖,G++?是super-λ當且僅當下面條件成立:

(1)G2K2∪mK1,K1,2∪mK1,K3∪mK1, 2K3,m是非負整數(shù);

(2)GK2∪K3,K2∪P3,P4,Pi是一條長為i?1 的路.

推論7(陳和孟[25]) 若G至少有兩條邊, 且G2K2, 2K2∪K1,K2∪P3, 則λ(G++?)=W(G++?).

定理54(陳和孟[26]) 給定圖G，G+??是max-λ當且僅當G至少有兩條邊, 且G2K2.

定理55(陳和周和黃[27]) 所有的連通變換圖G?+?是max-λ.

定理56(陳和孟[23]) 給定圖G, 若G???是連通的, 則λ(G???)=δ(G???).

7.2 圈邊連通性

設G是連通圖.G的一個邊割是它的邊子集F?E(G)使G?F中至少有兩個連通分支. 圖G的圈邊割是它的一個邊割F使得G?F至少有兩個連通分支包含圈. 圈邊連通度cλ(G) 是最小圈邊割的基數(shù). 所有的圈可分圖G滿足cλ(G)≤?(G)[28], 這里?(G)=min{?(X)=[X,] :X能導出G的最短圈}.

定理57(陳,朱,江[29])對于一個圖G,G++?是連通的且是圈可分的當且僅當G至少包含兩條邊,G/=2K2且G/=K1,2∪mK1,m≥0.

推論8(陳, 朱, 江[29]) 對于一個圖G,G++?是連通的且是圈可分的當且僅當G至少包含三條邊, 或G=2K2∪mK1,m≥1.

定理58(陳, 朱, 江[29]) 對于一個圖G, 若G++?是連通的且是圈可分的, 則

定理59(陳, 朱, 江[29]) 設圖G是連通的, 且G++?是連通的且是圈可分的, 則

8 拓撲指標

一個分子圖是把分子的原子看作圖的點, 把分子的鍵看作圖的邊得到的. 分子圖的圖理論的不變量被認為是拓撲指標, 用來預測相應分子的性質(zhì).

8.1 Zagreb 指標

第一和第二Zagreb指標是最早的著名拓撲指標之一,是Gutman等人在文獻[30]中引入的,他們用來測量全π-電子能對化學結(jié)構(gòu)的依賴性. 第一Zagreb和第二Zagreb指標分別定義為：

和

圖G的補圖的所有邊的和,這樣的不變量叫做Zagreb補指標.更確切地,圖G的第一第二Zagreb補指標在[31]中分別定義為:

和

在[32]中, De 定義了

在[33]中, 對正整數(shù)k∈{1,2,3}, 定義了則ξ1(G) 是G邊數(shù)的兩倍,ξ2(G) 是第一Zagreb 指標.

定理60(Hosamani 和Gutman[33]) 若G是階為n的圖, 且邊數(shù)為m, 則

推論9(Hosamani 和Gutman[33]) 若G是階為n的圖, 且邊數(shù)為m, 則

8.2 F-指標

一個拓撲指標在[30]中被證明能影響全π-電子能, 這個指標被定義為圖頂點的度的立方的和. Furtula 等人在[34]中研究了這個指標并且給出了一些基本性質(zhì). 他們把這個指標命名為“遺忘拓撲指標”或F-指標, 記為F(G), 因此

Ranjini等人在[35]中引入了新的Zagreb指標:

定理61(De[32]) 若G是階為n的圖, 且邊數(shù)為m, 則

定理62(De[32]) 若G是階為n的圖, 且邊數(shù)為m, 則

定理63(De[32]) 若G是階為n的圖, 且邊數(shù)為m, 則

定理64(De[32]) 若G是階為n的圖, 且邊數(shù)為m, 則

定理65(De[32]) 若G是階為n的圖, 且邊數(shù)為m, 則

定理66(De[32]) 若G是階為n的圖, 且邊數(shù)為m, 則

定理67(De[32]) 若G是階為n的圖, 且邊數(shù)為m, 則

定理68(De[32]) 若G是階為n的圖, 且邊數(shù)為m, 則

8.3 NK-指標

在1984, Narumi 和Katayama 在[36]中引入了圖的一個乘法的不變量，用于表示飽和烴的碳骨架，并命名為“簡單拓撲指標”. Tomovic 和Gutman 在[37]中把這個指標重新命名為“Narumi-Katayama 指標”或“NK-指標”并且記為NK(G). 圖的Narumi-katayama指標定義為所有頂點度的乘積, 即

Eliasi, Iranmanesh和Gutman在[38]中引入了一個新乘法的圖的不變量稱為乘積形式的Zagreb 指標，其定義為:

定理69(De[39]) 若G是階為n的圖, 且邊數(shù)為m, 則

定理70(De[39]) 若G是階為n的圖, 且邊數(shù)為m, 則等號成立當且僅當G是正則圖.

定理71(De[39]) 若G是階為n的圖, 且邊數(shù)為m, 則

等號成立當且僅當G是正則圖.

定理72(De[39]) 若G是階為n的圖, 且邊數(shù)為m, 則

等號成立當且僅當G是正則圖.

定理73(De[39]) 若G是階為n的圖, 且邊數(shù)為m, 則

定理74(De[39]) 若G是階為n的圖, 且邊數(shù)為m, 則

等號成立當且僅當G是正則圖.

定理75(De[39]) 若G是階為n的圖, 且邊數(shù)為m, 則

等號成立當且僅當G是正則圖.

定理76(De[39]) 若G是階為n的圖, 且邊數(shù)為m, 則

等號成立當且僅當G是正則圖.

9 譜

圖G的鄰接矩陣是n×n矩陣A(G):=(auv), 其中auv是連接頂點u和v的邊數(shù). 矩陣A(G)的特征多項式叫做圖G的特征多項式, 記為PG(λ).

定理77(Cvetkovi′c 和Doob 和Sachs[40])設G是一個有n個點,m條邊的r?正則圖(r>1). 如果G的特征值是λ1≥λ2≥···≥λn, 則G+++有m?n個特征值是-2, 其余的2n個特征值是:

由定理77證明可得:

定理78(顏和許[41]) 設G是一個有n個點,m條邊的r?正則圖. 如果G的特征值是λ1≥λ2≥···≥λn, 則

10 譜半徑

設G是一個階為n的簡單圖, 設A(G)為圖G的鄰接矩陣. 圖G的譜半徑ρ(G)定義為鄰接矩陣A(G) 的最大的特征值.

定理79(林和束[3]) 設G是一個有n≥3 個點,m條邊的連通圖. 則

定理80(林和束[3]) 設G是一個有n≥2 個點,m≥2 條邊的連通圖, 且G/=2K2. 則

定理81(林和束[3]) 設G是一個有n≥3 個點,m條邊的連通圖. 則

定理82(林和束[3]) 設G是一個有n≥2 個點,m條邊的連通圖, 且G不是星圖. 則

定理83(林和束[3]) 設G是一個有n≥3 個點,m條邊的連通圖并且沒有孤立點. 則

定理84(林和束[3]) 設G是一個有n≥2 個點,m條邊的連通圖并且沒有孤立點. 則

定理85(林和束[3]) 設G是一個有n≥3 個點,m條邊的連通圖并且沒有孤立點. 則

定理86(林和束[3]) 設G是一個有n≥3 個點,m條邊的連通圖并且沒有孤立點, 又G既不是K3也不是星圖. 則

11 Laplacian 譜

設D(G) := (dij) 是n×n的矩陣,dii=dG(vi) 且dij= 0,i/=j. 矩陣D(G) 和L(G) =D(G)?A(G) 分別是圖G的度矩陣和Laplacian矩陣. 圖G的Laplacian 多項式, Laplacian 譜和Laplacian 特征值分別是特征多項式L(λ,G)=det(λI?L(G)),L(G)的譜和其特征值.

定理87(鄧和Kelmans 和孟[42]) 設G是一個有n個點,m條邊的r?正則圖. 則

定理88(鄧和Kelmans 和孟[42]) 設G是一個有n個點,m條邊的r?正則圖, 并且設s=n+m. 則

12 控制

在圖G中如果一個點和邊是關聯(lián)的, 則稱這樣的點和邊是相互覆蓋的. 點覆蓋是覆蓋圖G中所有邊的點集,邊覆蓋是覆蓋圖G中所有點的邊集. 圖G的點覆蓋的最小基數(shù)叫做G的點覆蓋數(shù), 記為β(G). 圖G的邊覆蓋的最小基數(shù)叫做G的邊覆蓋數(shù), 記為β1(G).

如果V?S中的每個點在S中至少有一個鄰點, 則S?V(G)是一個控制集. 圖G的所有控制集的最小基數(shù)叫做G的控制數(shù), 記為γ(G). 邊控制的概念是由Mitchell 和Hedetniemi在[43]中提出的, 如果不在X中的每條邊在X中有一些相鄰的邊, 則邊集E(G)的子集X叫做圖G的邊控制集. 圖G的邊控制數(shù)γ′(G)是G的所有邊控制集的最小基數(shù)[43].

Sampathkumar 和Latha在[44]中引入了強控制和弱控制的概念. 若uv∈E(G), 則u和v相互控制. 進一步, 如果dG(u) ≥dG(v), 則u強控制v且v弱控制u. 如果V(G)?D中的每個點v被D中的一些點強控制, 則集合D?V(G)是G的強控制集(sd?set).G的強控制數(shù)γs(G)是強控制集的最小基數(shù). 類似地, 如果V(G)?W中的每個點被W?V(G)中的點弱控制，則W被稱作G的弱控制集(wd?set).G的弱控制數(shù)γw(G) 是wd?set的最小基數(shù).

Ayta?c和Turaci對Gxy+的控制數(shù)給出了一些界[45]. Jebitha 和Joseph 對G+?+的控制數(shù)給出了一些上界[46],Jebitha 和Joseph 引進了一個新參數(shù)叫做圖G的獨立邊控制數(shù)(記為從而對任何圖G確定了G?+?的控制數(shù)[47].

定理89(Ayta?c 和Turaci[45])設H是有n個點的連通圖并且僅包含一個懸掛點. 若對dH(u)=1 和v∈NH(u),圖G=H?euv有n個點, 且是r?正則的, 則

定理90(Jebitha 和Joseph[46]) 對任何圖G,γ(G)≤γ(G+?+)≤γ(G)+2 且界是緊的.

定理91(Jebitha 和Joseph[46]) 設G是階為n≥5的連通圖. 則且界是緊的.

定理92(Jebitha 和Joseph[46]) 若G是一個連通圖, 且?(G)=n?2, 則γ(G+?+)≤3.

定理93(Jebitha 和Joseph[46]) 如果一個圖G的diam(G)=2, 則γ(G+?+)≤δ(G)+1 且界是緊的.

定理94(Jebitha 和Joseph[46]) 對任何連通圖G, ?(G)

定理95(Jebitha 和Joseph[46]) 設G是階為n >2的連通圖, ?(G) =n?1 且v是一個度為?(G)的頂點.則γ(G+?+)=2 當且僅當〈N(v)〉 是非空的并且包含K1或K2或同構(gòu)于K1,r,r≥2.

定理96(Ayta?c 和Turaci[45]) 設G是一個有n個點,m條邊的連通圖, 則γ(G?++)≤1+γ′(G).

定理97(Ayta?c 和Turaci[45]) 設G是一個有n個點連通圖, 并且是r?正則的. 若n>2r+1, 則

定理98(Ayta?c 和Turaci[45]) 設G是一個有n個點連通圖, 并且是r?正則的. 若n<2r+1, 則

定理99 (Ayta?c 和Turaci[45]) 設G是一個有n個點,m條邊的連通圖, 則γ(G+?+)≤β(G).

定理100(Ayta?c 和Turaci[45])設G是一個有n個點,m條邊的連通圖,若G僅包含一個懸掛點且點的最大度為?(G)=n?1, 則γ(G+?+)=2.

定理101(Ayta?c 和Turaci[45]) 設G是一個有n個點的連通圖, 并且是r?正則的. 若r >3, 則γ(G??+)=γw(G??+)≤β(G) 和γs(G??+)≤n?β1(G).

定理102(Jebitha 和Joseph[47]) 對任何圖G,γ(G?+?)≤3. 進一步,

(i)γ(G?+?)=1 當且僅當δ(G)=0;

(ii)γ(G?+?)=2 當且僅當diam(G)≥3 或G有一個邊數(shù)為2的匹配.