廣義剖分冠點(diǎn)圖的鄰接特征多項(xiàng)式

盧鵬麗，武雨末

（蘭州理工大學(xué)計(jì)算機(jī)與通信學(xué)院，甘肅蘭州730050）

廣義剖分冠點(diǎn)圖的鄰接特征多項(xiàng)式

盧鵬麗，武雨末

（蘭州理工大學(xué)計(jì)算機(jī)與通信學(xué)院，甘肅蘭州730050）

冠圖是由圖G與圖H經(jīng)過(guò)圖操作得到的組合圖，已經(jīng)有一些冠圖被定義及研究。但是現(xiàn)有文獻(xiàn)中的冠圖定義均是將圖H進(jìn)行n次拷貝，得到的圖G與圖H的各類(lèi)冠圖。將冠圖的定義推廣為一般化的情形，即將原來(lái)n個(gè)相同的圖H一般化為任意圖H1，H2，…，Hn，定義了一類(lèi)新的廣義剖分冠點(diǎn)圖。首先在圖G的每條邊上添加一個(gè)新的頂點(diǎn)得到其剖分圖S（G）；將V（G）中的第i個(gè)頂點(diǎn)與Hi中的所有頂點(diǎn)連接；這樣由剖分圖S（G）和圖H1， H2，…，Hn構(gòu)造的圖稱(chēng)為廣義剖分冠點(diǎn)圖，記為圖應(yīng)用分塊矩陣、矩陣的冠、舒爾補(bǔ)定理等確定了廣義剖分冠點(diǎn)圖的鄰接特征多項(xiàng)式；提出了構(gòu)造無(wú)窮鄰接同譜圖類(lèi)的方法且給出了示例。

組合圖；廣義剖分冠點(diǎn)圖；鄰接特征多項(xiàng)式；正則圖；同譜圖

本文只討論無(wú)向簡(jiǎn)單圖。圖G= (V（G），E（G）)，其中頂點(diǎn)集和邊集分別為V（G）=｛v1，v2，…，vn｝， E（G）=｛e1，e2，…，em｝圖G的鄰接矩陣記為A（G），由元素aij組成，當(dāng)頂點(diǎn)vi與vj相鄰時(shí)為1，否則為0。圖G的關(guān)聯(lián)矩陣記為R（G），是由元素bij組成，當(dāng)頂點(diǎn)vi與邊ej相鄰時(shí)為1，否則為0。頂點(diǎn)vi的度記為dG（i）。圖G的度矩陣記為D（G），是對(duì)角線上元素為dG（i）的n× n對(duì)角矩陣。并且有R（G）R（G）T=A（G）+ D（G）。圖G的鄰接特征多項(xiàng)式記為

式中:In表示大小為n的單位矩陣。由鄰接特征多項(xiàng)式得到的特征值稱(chēng)為鄰接特征值，從大到小排序?yàn)棣薾≥λn-1≥…≥λ2≥λ1。擁有相同鄰接特征多項(xiàng)式的圖叫做A-同譜圖［1-3］。

冠圖是由兩個(gè)圖，圖G與圖H經(jīng)過(guò)圖操作得到的復(fù)雜圖。已經(jīng)有一些類(lèi)的冠圖被定義和研究，如冠邊圖、冠點(diǎn)圖、鄰居冠圖等。冠圖的譜難以計(jì)算，對(duì)于冠圖的研究主要是將其表示為原圖的譜并用于實(shí)際的計(jì)算中。本文擴(kuò)大了冠點(diǎn)圖的范圍，定義了廣義剖分冠點(diǎn)圖并確定了其特征多項(xiàng)式，給出了構(gòu)造無(wú)窮鄰接同譜圖類(lèi)的方法及示例。

1 主要引理

計(jì)算鄰接特征多項(xiàng)式的時(shí)候采用了舒爾補(bǔ)定理和矩陣的冠，下面給出相關(guān)引理。

引理1（舒爾補(bǔ)定理）［4］:設(shè)矩陣A為n×n分塊矩陣:

式中:A11與A22為可逆方陣。則

引理2［5-6］:設(shè)矩陣M為n×n實(shí)對(duì)稱(chēng)矩陣，jn是長(zhǎng)度為n的全1列向量。則矩陣M的冠，記為ΓM（x），是矩陣(xIn-M)-1的所有元素之和，即

特別地，當(dāng)矩陣M的每一行元素之和都等于t時(shí):

對(duì)于n個(gè)頂點(diǎn)的r-正則圖G，鄰接矩陣A（G）的每一行之和都為度r，因此

2 廣義剖分冠點(diǎn)圖的鄰接矩陣

冠圖是由兩個(gè)圖經(jīng)過(guò)圖操作得到的組合圖。圖G與圖H的冠圖［7］定義為:將圖H復(fù)制次，然后將第i個(gè)H的所有頂點(diǎn)與V（G）第i個(gè)頂點(diǎn)連接，這樣由G和｜V（G）｜個(gè)H構(gòu)造的圖，稱(chēng)之為圖G與圖H的冠圖。文獻(xiàn)［8-12］中定義了各類(lèi)冠圖，如邊冠圖、鄰居冠圖、剖分鄰居冠圖等。但是都是將圖H進(jìn)行n次拷貝，得到的圖G與圖H的組合圖。

本文將冠圖的定義推廣為一般化的情形，即將原來(lái)n個(gè)相同的圖H一般化為任意圖H1，H2，…，Hn，定義了廣義剖分冠點(diǎn)圖。首先在圖G的每條邊上添加一個(gè)新的頂點(diǎn)得到其剖分圖S（G）；將Hi中的所有頂點(diǎn)與V（G）中的第i個(gè)頂點(diǎn)連接；這樣由剖分圖S（G）和圖H1，H2，…，Hn構(gòu)造的圖稱(chēng)為廣義剖分冠點(diǎn)圖，記為圖

其中，

3 圖S（G）☉Hi的鄰接特征多項(xiàng)式

定理1設(shè)圖G有n個(gè)頂點(diǎn)m條邊。Hi為任意圖，i=1，2，…，n。那么

證明:設(shè)圖Hi有ti個(gè)頂點(diǎn)，由式（1）及鄰接特征多項(xiàng)式的定義并運(yùn)用舒爾補(bǔ)定理可知:

記

又因?yàn)?/p>

所以

因此，得證。

推論1圖G有n個(gè)頂點(diǎn)，m條邊。若對(duì)于圖有那么

證明:若對(duì)于i=1，2，…，n，有ΓA(Hi)（λ）= ΓA(H)（λ），那么設(shè)

所以

由此，此推論的結(jié)果已證得。

由引理2及推論1可以得到下面的推論。

推論2圖G有n個(gè)頂點(diǎn)，m條邊。圖H1，H2，…，Hn均為t個(gè)頂點(diǎn)的r-正則圖，那么

由推論1可得下面的推論。

推論3r-正則圖G有n個(gè)頂點(diǎn)，m條邊，H為一個(gè)任意圖。設(shè)圖G的第i個(gè)鄰接特征值為λi（G），那么圖G與n個(gè)圖H構(gòu)成的剖分冠點(diǎn)圖的鄰接特征多項(xiàng)式如下:

4 廣義剖分冠點(diǎn)圖的鄰接同譜圖

推論4G1和G2是兩個(gè)鄰接同譜的r-正則圖，若圖H1，H2，…，Hn的鄰接矩陣的冠相等，即

推論5圖G有n個(gè)頂點(diǎn)。取為一簇鄰接同譜圖族（其中Hi可有相同的），且那么任取這個(gè)鄰接同譜圖族中大小為n的子集與圖G所構(gòu)成的廣義剖分冠點(diǎn)圖之間是彼此鄰接同譜的。

對(duì)于推論5，我們給出如下例子:如圖1所示，圖G2和圖G3是鄰接同譜圖，其鄰接特征多項(xiàng)式均為且它們鄰接矩陣的冠值也相等，即

圖1 例子中用到的三個(gè)圖Fig．1 Three graphs used in the example

那么取鄰接同譜圖族｛Hi｜H1=G2，H2=G3，H3=G2，H4=G3，H5=G2，H6=G3｝。任取這個(gè)鄰接同譜圖族中大小為3的子集，即｛H1，H3，H5｝、｛H2，H4，H6｝、｛H1，H2，H3｝、｛H2，H3，H4，｝，與圖G所構(gòu)成的廣義剖分冠點(diǎn)圖（如圖2就是圖G與｛H1，H2，H3｝構(gòu)成的廣義剖分冠點(diǎn)圖的鄰接特征多項(xiàng)式均相等，為

即這些廣義剖分冠點(diǎn)圖之間也是鄰接同譜的。

5 結(jié)論

本文推廣了剖分冠點(diǎn)圖的定義，得到了可以冠任意圖的廣義剖分冠點(diǎn)圖。可以對(duì)其他冠圖作進(jìn)一步的研究，嘗試得到其廣義定義下的圖譜。巧妙地得到了無(wú)窮的鄰接同譜圖類(lèi)，這一結(jié)論對(duì)研究化學(xué)圖論有益。

［1］BROUWER A E，HAEMERS W H．Spectra of graphs［M］．New York:Springer，2012．

［2］CVETKOVIC D M，DOOB M，SACHS H．Spectra of graphs:theory and applications［M］．3rd ed．Heidelberg: Johann Ambrosius Barth，1995．

［3］CVETKOVIC D M，ROWLINSON P，SIMIC S．An introduction to the theory of graph spectra［M］．Cambridge:Cambridge University Press，2009．

［4］ZHANG Fuzhen．The schur complement and its applications［M］．US:Springer，2005．

［5］CUI Shuyu，TIAN Guixian．The spectrum and the signless Laplacian spectrum of coronae［J］．Linear algebra and its applications，2012，437（7）:1692-1703．

［6］MCLEMAN C，MCNICHOLAS E．Spectra of coronae［J］．Linear algebra and its applications，2011，435（5）:998-1007．

［7］FRUCHT R，HARARY F．On the corona of two graphs［J］．Aequationes mathematicae，1970，4（1）:264．

［8］LIU Xiaogang，LU Pengli．Spectra of subdivision-vertex and subdivision-edge neighbourhood coronae［J］．Linear algebra and its applications，2013，438（8）:3547-3559．

［9］GOPALAPILLAI I．The spectrum of neighborhood corona of graphs［J］．Kragujevac journal of mathematics，2011，35（3）:493-500．

［10］HOU Yaoping，SHIU W C．The spectrum of the edge corona of two graphs［J］．Electronic journal of linear algebra，2010，20:586-594．

［11］WANG Shilin，ZHOU Bo．The signless Laplacian spectra of the corona and edge corona of two graphs［J］．Linear and multilinear algebra，2013，61（2）:197-204．

［12］LU Pengli，MIAO Yufang．A-spectra and Q-spectra of two classes of corona graphs［J］．Journal of Donghua university:English edition，2014，31（3）:224-228．

Adjacency characteristic polynomial of generalized subdivision corona vertex graph

LU Pengli，WU Yumo
（School of Computer and Communication，Lanzhou University of Technology，Lanzhou 730050，China）

Corona graph is a composite graph obtained by graph operation from two graphs G and H．Some classes of corona graphs have been defined and studied．However，all the corona graphs in the literatures were defined as all kinds of corona graphs of graph G and H，in which graph H was n copies of grap H．By generalizing n copies of graph to arbitrary graphs in the definition of corona，a new class of corona was defined:the generalized subdivision corona vertex graph．Let S（G）be the subdivision graph of graph G by inserting a new vertex into every edge of G．Joining the ith vertex of V（G）to every vertex of Hi，the generalized subdivision corona vertex graph from graph S（G）and graph H1，H2，…，Hnwas obtained，which was denoted byWith the help of block matrix，the coronal and Schur complement，the adjacency characteristic polynomial of the generalized subdivision corona vertex graph was determined．A method to construct infinite pairs of cospectral graphs was proposed and an example was given．

composite graph；generalized subdivision corona vertex graph；adjacency characteristic polynomial；regular graphs；cospectral graphs

10．11990／jheu．201511033

http：／／www．cnki．net／kcms／detail／23．1390．u．20160928．0936．010．html

O157．5；O157．6

A

1006-7043（2016）12-1739-04

盧鵬麗，武雨末．廣義剖分冠點(diǎn)圖的鄰接特征多項(xiàng)式［J］．哈爾濱工程大學(xué)學(xué)報(bào)，2016，37（12）:1739-1742．

2015-11-16．

2016-09-28．

國(guó)家自然科學(xué)基金項(xiàng)目（11361033）．

盧鵬麗（1973-），女，教授，碩士生導(dǎo)師．

盧鵬麗，E-mail:lupengli88＠163．com．

LU Pengli，WU Yumo．Adjacency characteristic polynomial of generalized subdivision corona vertex graph［J］．Journal of Harbin Engineering University，2016，37（12）:1739-1742．