侯勝哲

(吉林化工學院, 吉林 吉林 132022)

圖G1與圖G2的聯(lián)圖是指圖G1的每個頂點G2和的每個頂點相連的圖,記作G1∨G2.錐圖(cone graph)指的是圈Cm與空圖On的聯(lián)圖Cm∨On,記作Pm,n(如圖1).圖G中經(jīng)過每個頂點的圈稱為圖G的哈密頓圈;一個包含哈密頓圈的圖稱為哈密頓圖.圖G的鄰接矩陣A(G)的特征值及其重數(shù)叫做圖G的鄰接譜.使得圖G中相鄰兩點著不同顏色所需要的最少顏色數(shù),稱為圖G的色數(shù).

圖1 錐圖Pm,n

錐圖最早是Buckley和Harary[1]在研究廣義輪圖時提出的,但未正式命名,也未深入探究.Gallian[2]等人在研究優(yōu)美圖時,發(fā)表了數(shù)篇文章對錐圖進行了簡要說明.最近幾年,Daouda[3]研究了錐圖的生成樹的個數(shù);Bosco等[4]給出了錐圖的無線電平均D-距離數(shù)(radio mean D-distance number);徐連誠等[5]給出了錐圖的獨立數(shù)的確切值. Pan等[6]研究了錐圖的多重著色問題.Kook[7]研究了特殊錐圖的α-不變性.Alfaro等[8]研究了以任意圖為基圖所構(gòu)造的錐圖的沙堆群;吳寶豐等[9]研究了基于正則圖的錐圖的Q-譜確定性;鄭文萍在她的博士論文中[10]研究了錐圖等一系列圖的交叉數(shù)問題.

本文主要研究了多錐圖的色數(shù)、可平面性、鄰接矩陣、鄰接矩陣特征值(譜)、哈密頓性.

1 棱錐圖的色數(shù)與可平面性

輪圖(wheel graph)Wn(如圖2)的定義為圈Cm與一個點的聯(lián)圖,即Cm∨O1,易知Pm,1(如圖3)即為輪圖Wm;Pm,2為雙錐圖(如圖4,5,6).

圖2 輪圖Wm

圖3 棱錐Pm,1

圖4 雙錐圖Pm,2

定理1.1P3,1為完全圖K4,P4,2為完全3部圖K2,2,2,P4,n為完全3部圖K2,2,n.

證明事實上,P3,1為四面體(tetrahedral)骨架圖所對應(yīng)的平面圖;P4,2為八面體(octahedral)骨架圖對應(yīng)的平面圖,即K2,2,2(如圖5);P4,n為完全3部圖K2,2,n(如圖7).

圖5 P4,2為K2,2,2

圖6 棱錐圖Pm,2是平面

定理1.2當錐圖的頂點劃分盡可能少時,Pm,n可為4部圖.

證明在錐圖Pm,n=Cm∨On中,若Cm是偶圈時,Cm的頂點集可以用兩種顏色正常著色,空圖On中的點用第三種顏色,此時Pm,n為完全3部圖;若Cm是奇圈時,Cm的頂點集需要用三種顏色才能正常著色,而空圖On中的點和Cm中的每個點相鄰,故On中的點必須取另一種顏色.此時Pm,n需要4種顏色才能正常著色,把每種顏色看作一個劃分.故Pm,n是4部圖.

推論1.3錐圖Pm,n是四可著色的.

定理1.4錐圖Pm,n在n=1,2時是平面圖;錐圖Pm,n(m≤3,n≥3)是平面圖;錐圖Pm,n(m≥3,n≥3)不是平面圖.

證明(1)Pm,1與輪圖同構(gòu)顯然是平面圖,如圖6所示;對于Pm,2,O2中的點設(shè)為A和B,將A點與Cm的頂點的連邊按輪圖的平面圖Wm畫出,將B點放置在最外側(cè)的無界面,再分別連接Cm上的點,該種連接方式可以做到與Wm邊不交,這顯然是Pm,2的一個平面嵌入.

(2)對于P1,n,n≥3根據(jù)定義P1,n=C1∨On, 即為星圖K1,n, 顯然是平面圖.對于P2,n, 根據(jù)定義P2,n=C2∨On, 容易得到P2,n的一個平面嵌入(圖8), 易知P2,n是可平面的.

圖8 錐圖P2,n是平面

(3)對于P3,3, 我們有P3,3-E(C3)?K3,3(圖9和圖10),P3,3包含一個K3,3的子圖,根據(jù)Kuratowski定理,故其是非平面圖.當Pm,n(m≥3,n≥3),任取Cm中的三個點和On中的三個點, 在這六個點中間只保留Cm與On之間的邊,故形成了K3,3,所以Pm,n都包含了K3,3,知其都是非平面圖.

圖9 P3,3含有K3,3

圖10 K3,3

眾所周知,四色定理保證“每個平面圖都是四可著色的”,那么自然會問“每個四可著色的圖都是平面圖”對嗎?由推論1.2和定理1.3可知,答案是否定的,錐圖Pm,n就是一個反例.

2 錐圖的鄰接矩陣(譜)與哈密頓性

在本節(jié)中的圈Cm都滿足m≥3.在下面的定理3.3中分別用Pm,n來表示錐圖Pm,n的鄰接矩陣,Cm表示圈Cm的鄰接矩陣,On表示空圖On的鄰接矩陣,Em代表m階的單位陣.

對于錐圖Pm,n=Cm∨Om,給定一種頂點標號方式記為(*):先將Cm按照順時針方向進行標號v1,v2,…,vm,接著對其它n個獨立頂點進行任意標號vm+1,vm+2,…,vm+n.

例2.1畫圖(如圖11所示),并求出P4,6的鄰接矩陣,并驗證定理2.1.

圖11 P4,6

解：如圖12與定理2.1吻合.

圖12 A(P4,6)

引理2.1[11］在一個有向簡單圖(對于無向圖亦成立)的鄰接矩陣中,若能找到一組n個1,使得其中任意兩個1不在同一行也不在同一列,且不關(guān)于主對角線對稱,則該圖為哈密爾頓圖.

定理2.2錐圖Pm,n(m≥n)是哈密頓圖.

證明當m≥n時,在右上角的分塊矩陣In,m、左下角的分塊矩陣Im,n中顯然可以找到n個既不同行也不同列的1,根據(jù)引理2.1可知,錐圖Pm,n(m≥n)是哈密頓圖.

注: (1)定理2.2也可以利用定義法證明,按照(*)的標號方式,頂點v的角標按照1-(m+i1)-2-(m+i2)-…-(m+in)-n-(n+1)-(n+2)-…-m,其中i1,i2,…,im∈[1,n]∩N+,進行標號,便得到至少一個哈密頓圈,故其為哈密頓圖.

(2)m的值要大于等于n,例如P4,6就不行,但是P4,3可以,1-(m+i1)-2-(m+i2)-3-(m+i3)-4-1,其中i1i2,…,i3∈[1,3]∩N+.

當然Pm,n不一定是歐拉圖很好判斷,因為每個點的度不一定是偶的.

證明

例2.2利用P6,7、C6和P7,5、C7驗證定理2.3的結(jié)論.

解：(1)P6,7的特征多項式為f(A,P6,7)=(x-1)2x6(x+1)2(x+2)(x2-2x-42),C6的特征多項式為f(A,C6)=(x-2)(x-1)2(x+1)2(x+2), 可以看出除了2這個根以外,P6,7的特征根中必含有C6的特征根.

(2)P7,5的特征多項式為f(A,P7,5)=(x-7)x4(x+5)(x3+x2-2x-1)2,C7的特征多項式為f(A,C7)=(x-2)(x3+x2-2x-1)2, 可以看出除了2這個根以外,P7,5的特征根中必含有C7的特征根.

證明