盧鵬麗，武雨末

（蘭州理工大學計算機與通信學院，甘肅蘭州730050）

廣義剖分冠點圖的鄰接特征多項式

盧鵬麗，武雨末

（蘭州理工大學計算機與通信學院，甘肅蘭州730050）

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

組合圖；廣義剖分冠點圖；鄰接特征多項式；正則圖；同譜圖

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

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

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

1 主要引理

計算鄰接特征多項式的時候采用了舒爾補定理和矩陣的冠，下面給出相關引理。

引理1（舒爾補定理）［4］:設矩陣A為n×n分塊矩陣:

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

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

特別地，當矩陣M的每一行元素之和都等于t時:

對于n個頂點的r-正則圖G，鄰接矩陣A（G）的每一行之和都為度r，因此

2 廣義剖分冠點圖的鄰接矩陣

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

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

其中，

3 圖S（G）☉Hi的鄰接特征多項式

定理1設圖G有n個頂點m條邊。Hi為任意圖，i=1，2，…，n。那么

證明:設圖Hi有ti個頂點，由式（1）及鄰接特征多項式的定義并運用舒爾補定理可知:

記

又因為

所以

因此，得證。

推論1圖G有n個頂點，m條邊。若對于圖有那么

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

所以

由此，此推論的結果已證得。

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

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

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

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

4 廣義剖分冠點圖的鄰接同譜圖

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

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

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

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

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

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

5 結論

本文推廣了剖分冠點圖的定義，得到了可以冠任意圖的廣義剖分冠點圖?？梢詫ζ渌趫D作進一步的研究，嘗試得到其廣義定義下的圖譜。巧妙地得到了無窮的鄰接同譜圖類，這一結論對研究化學圖論有益。

［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

盧鵬麗，武雨末．廣義剖分冠點圖的鄰接特征多項式［J］．哈爾濱工程大學學報，2016，37（12）:1739-1742．

2015-11-16．

2016-09-28．

國家自然科學基金項目（11361033）．

盧鵬麗（1973-），女，教授，碩士生導師．

盧鵬麗，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．