完美非奇異圖和完美奇異圖

梁文君 馬曉玢

摘 ?要：定義并確定了兩種類型的圖：當(dāng)[n（≥2）]階的連通圖的所有[k（≥2）]階連通誘導(dǎo)子圖均為非奇異時，稱其為完美非奇異圖；當(dāng)[n（≥3）]階連通圖的所有[k（≠2）]階連通誘導(dǎo)子圖均為奇異時，稱其為完美奇異圖.

關(guān)鍵詞：奇異性；圖的秩；鄰接矩陣

[ ? 中圖分類號 ? ?]О157.6[ ? ?文獻(xiàn)標(biāo)志碼 ? ] ?A

Perfect Nonsingular Graphs and Perfect Singular Graphs

LIANG Wenjun，MA Xiaobin

（School of Mathematics and Big Data，Anhui University of Science and Technology，Huainan 232001，China）

Abstract：Two types of diagrams are defined and identified：A connected graph of order [n（≥2）] is called perfect nonsingular if all its connected induced subgraphs of order [k（≥2）] are nonsingular；A connected graph of order [n（≥3）]is called perfect singular if all its connected induced subgraphs of order [k（≠2）] are singular.

Key words：singularity；rank of graphs；adjacency matrixs

圖的奇異性在化學(xué)中體現(xiàn)于Hückel分子軌道模型，如果分子圖是奇異的，那么相應(yīng)的化合物是具有高度活性和不穩(wěn)定性，或者說是不存在的.[1，2]1957年，Collatz 和 Sinogowitz[3]提出了刻畫所有奇異圖的問題.本文研究的是簡單圖.[A（G）=（aij）n×n]是圖[G=（V（G），E（G））]的鄰接矩陣，其中，若[vi]和[vj]間是鄰接的，則[aij=aji=1]；否則，[aij=0].[n]階圖[G]的秩，記為[r（G）]，也是[A（G）]的秩.若[A（G）]是非奇異的，則[G]是非奇異的，[r（G）=n].同樣地，若[A（G）]是奇異的，則[G]是奇異的，即[r（G）

1 預(yù)備知識

引理1 設(shè)[Kn]是[n]階的完全圖，則[Kn]是非奇異的，除非[n=1].

引理2 設(shè)[Pn]是[n]階的路徑，則當(dāng)且僅當(dāng)[n]是偶數(shù)時[Pn]是非奇異的.

引理3 設(shè)[Cn]是[n]階的圈，[Cn]是非奇異的，除非[n=0（mod4）].

引理4 設(shè)[Km，n-m]是[n]階的完全二部圖，則[Km，n-m]是奇異的，除非[m=1]且[n=2].

Cvetkovi? 和 Gutman[1，4]證明，若[B]是一個二部的，且無長度為[0（mod4）]的圈，則[r（B）=2m（B）]，其中[m（B）]是[B]的匹配數(shù).這是引理2的一個推廣，表明當(dāng)且僅當(dāng)[B]有一個完美匹配時，它是非奇異的.Guo[5]等確定了所有非奇異單圈圖.Li[6]等刻畫了深度為1的單圈圖的線圖的奇異性.尹慈[7]等對包含兩個三角形的秩為7的雙圈圖進(jìn)行了刻畫，彭?xiàng)頪8]等也對正慣性指數(shù)為2的樹、單圈和雙圈圖進(jìn)行了刻畫.對于二部圖[9]、雙圈圖[10]和三圈圖[11]，已確定了相應(yīng)的秩集，但對非奇異圖的刻畫仍未確定.Chen[12]等也刻畫了三種有向圖的奇異性.

若[Φ=V（H）?V（G）]且[E（H）?E（G）]，則圖[H=（V（H），E（H））]稱為圖[G=（V（G），E（G））]的子圖.從而，對于任意兩個頂點(diǎn)[u，v∈V（H）]，當(dāng)且僅當(dāng)[uv∈E（G）]時，[uv∈E（H）]，那么，[H]稱為[G]的誘導(dǎo)子圖.因此，誘導(dǎo)子圖是由其頂點(diǎn)集決定的.若[n（≥2）]階連通圖[G]的所有[k（≥2）]階的連通誘導(dǎo)子圖都是非奇異的，那么，[n（≥2）]階的連通圖[G]是完美非奇異的，1階的圖是奇異的.若當(dāng)[n（≥3）]階連通圖所有[k（≠2）]階的連通誘導(dǎo)子圖都是奇異時，那么，[n（≥3）]階連通圖是完美奇異的，進(jìn)一步得知2階連通圖是非奇異的.

本文確定了這兩種類型的圖，進(jìn)一步定義了弱完美非奇異圖和弱完美奇異圖.如果[n（≥3）]階的連通圖的每個3階連通誘導(dǎo)子圖是非奇異的，則此連通圖是弱完美非奇異的.如果每個[n（≥4）]階連通圖的3或4階連通誘導(dǎo)子圖是奇異的，則此連通圖是弱完美奇異的.

定理1 設(shè)[G]是[n（≥5）]階連通圖：（i）[G]是弱完美非奇異圖，當(dāng)且僅當(dāng)[G]是完美非奇異的或[G=Kn].（ii）[G]是弱完美奇異圖，當(dāng)且僅當(dāng)[G]是完美奇異的或[G=Km，n-m].

2 完美非奇異圖

定理2 設(shè)[G]是[n（≥3）]階連通圖，則以下三項(xiàng)等價：（i）[G]是弱完美非奇異圖.（ii）[G]是完美非奇異圖.（iii）[G=Kn].

證明 用（i）→（iii），（iii）→（ii）和（ii）→（i）來證明等價性.（ii）→（i）顯而易見.需要注意的是，完全圖的每一個連通誘導(dǎo)子圖仍然是一個完全圖，除非它的階數(shù)為1，從而由引理1可得，它是非奇異的.（iii）→（ii）也得證.

而對于（i）→（iii），可以假設(shè)[G]是弱完美非奇異圖且[V（G）=n≥3].若[n=3]，那么[G=K3].再對[n]進(jìn)行歸納.首先，假設(shè)[4≤n≤k]時[G]是一個完全圖.再考慮[G]是弱完美非奇異圖且[V（G）=k+1]，則[G]包含一個[k]階的弱完美非奇異誘導(dǎo)子圖[H].根據(jù)歸納假設(shè)，有[H=Kk].如果將[v]表示為唯一的頂點(diǎn)，使得[v∈V（G）＼V（Kk）]，因?yàn)閇G]是連通的，則[v]與某個頂點(diǎn)[x∈V（Kk）]相鄰.若假設(shè)[G≠Kk+1]，那么存在某個頂點(diǎn)[y∈V（Kk）]，使得[y]在[G]中不與[v]相鄰.現(xiàn)在[G]包含一個由頂點(diǎn)集[v，x，y]誘導(dǎo)出的3階連通子圖，它與[P3]同構(gòu)，由引理2證明它是奇異的，與[G]是弱完美非奇異圖矛盾.因此，[G=Kk+1]，歸納完成.

定理的條件[n≥3]確保[G]至少包含一個3階的子圖，唯一的2階連通圖[K2]是完全非奇異的，得到推論1.

推論1 設(shè)[G]是[n（≥2）]階連通圖，則當(dāng)且僅當(dāng)[G=Kn]時，[G]是完美非奇異的.

3 完美奇異圖

對于連通圖[G]，如果其所有3階的連通誘導(dǎo)子圖都是非奇異的，則[G]是非奇異的.如果所有3階的連通誘導(dǎo)子圖都是奇異的，[G]是可以為非奇異的.例如，任何偶數(shù)[n（≥4）]階的路徑[Pn]都是非奇異的，盡管其所有3階的連通誘導(dǎo)子圖都是奇異的.因此，當(dāng)連通圖的3階或4階誘導(dǎo)連通子圖均為奇異時，定義該連通圖為弱完美奇異.

定理3 設(shè)[G]為[n（≥4）]階連通圖.則以下三個條件是等價的：（i） [G]是弱完美奇異圖.（ii）[G]是完美奇異圖.（iii）[G=Km，n-m]，其中[1≤m≤n-1].

證明 用（i）→（iii），（iii）→（ii）和（ii）→（i）證明等價性.（ii）→（i）顯而易見.當(dāng)[G]是完全二部圖時，它的每一個階至少為2的連通誘導(dǎo)子圖也是完全二部圖，由引理4可得，[G]是奇異的除非階為2，則（iii）→（ii）是可以確定的.

對于（i）→（iii），可以假設(shè)[G]是弱完美奇異圖且[V（G）=n≥4].若[n=4]，可見[C3]不是[G]的誘導(dǎo)子圖，否則它包含一3階的非奇異連通誘導(dǎo)子圖，那么，有[G=C4=K2，2]或[G=P4].如果[G=P4]，由引理2可得它是非奇異的，與假設(shè)的矛盾.因此[G=K2，2].

當(dāng)[n≥4]時，可以使用歸納法完成證明.首先，假設(shè)[4≤n≤k]時，[G=Km，n-m].再考慮一個[k+1（≥5）]階的弱完美奇異圖[G].根據(jù)歸納假設(shè)，[G]必包含了一個[k]階的弱完美奇異圖[H]作為它的誘導(dǎo)子圖，即[Km，k-m].令[V（Km，k-m）=X?Y]，其中[X={x1，x2，…，xm}]和[Y={y1，y2，…yk-m}]是兩個劃分集.設(shè)[v=V（G）＼V（Km，k-m）]，假設(shè)[vx1∈E（G）]不具有一般性，因?yàn)镃3不包含在[G]中，那么對于任意[j]有[vyj?E（G）].進(jìn)一步考慮，若當(dāng)[2≤i≤m]，[vxi?E（G）]時，那么由點(diǎn)集[v，x1，y1，xi]誘導(dǎo)出的一個連通誘導(dǎo)子圖[P4]是非奇異的.這就意味著對于每一個[i]，[vxi∈E（G）].因此[G=Km，k-m+1]，歸納完成.

由引理2或引理4可得，[K2，1]也是奇異的，那么得出推論2.

推論2 設(shè)[G]是[n（≥3）]階連通圖.當(dāng)[1≤m≤n-1]時，當(dāng)且僅當(dāng)[G=Km，n-m]，G是完美奇異的.

參考文獻(xiàn)

[1]D.Cvetkovi?，I.Gutman，N.Trinajstíc.Graph theory and molecular orbitals II[J].Croat.Chem.Acta.，44（1972），365-374.

[2]E.Hückel.Quantentheoretische Beitr?ge zum Benzolproblem[J].Z.Phys.，70 （1931），204-286.

[3]L.Collatz，U.Sinogowitz.Spektren endlicher Grafen[J].Abh.Math.Sem.Univ.Hamburg，21（1957），63-77.

[4]D.Cvetkovi?，I.Gutman.The algebraic multiplicity of the number zero in the spectrum of a bipartite graph[J].Matematicki Vesnik，Beograd，9（1972），141-150.

[5]J.Guo，W.Yan，Y.-N.Yeh.On the nullity and the matching number of unicyclic graphs[J].Linear Algebra Appl.，431（2009），1293-1301.

[6]H.Li，Y.Fan，L.Su.On the nullity of the line graph of unicyclic graph with depth one[J].Linear Algebra Appl.，437（2012），2038-2055.

[7]尹慈，馬曉玢.包含兩個三角形的秩為7的雙圈圖刻畫[J].牡丹江師范學(xué)院學(xué)報(bào)：自然科學(xué)版，2021（3）：1-5.

[8]彭?xiàng)睿@亞，朱娜.幾類正慣性指數(shù)為2的圖的刻畫[J].牡丹江師范學(xué)院學(xué)報(bào)：自然科學(xué)版，2021（1）：1-6.

[9]Y.Fan，K.Qian.On the nullity of bipartite graphs[J].Linear Algebra Appl.，430（2009），2943-2949.

[10]S.Hu，X.Tan，B.Liu.On the nullity of bicyclic graphs[J].Linear Algebra Appl.，429（2008），1387-1391.

[11]B.Cheng，B.Liu.On the nullity of tricyclic graphs[J].Linear Algebra Appl.，434（2011），1799-1810.

[12]X.Chen，J.Yang，X.Geng，L.Wang.Singularity of oriented graphs from several classes[J].B.AUST Math.Soc.，102（1）（2020），7-14.

編輯：琳莉