輪形圖K1∨Cn和扇形圖K1∨Pn的解析

汪小黎，王 曉

(商洛學(xué)院 數(shù)學(xué)與計算科學(xué)系,陜西商洛 726000)

1引言及引用定理

本文所研究的圖均為有限、無向、簡單圖。設(shè)G=(V(G),E(G))表示一個圖，V(G)和 E(G)分別表示圖G的頂點集和邊集。圖Pn表示n個頂點的路，圖Cn表示n個頂點的圈，聯(lián)圖G1∨G2表示用G1中的每一個頂點連結(jié)G2中所有頂點且G1和G2各自的邊保持不變所得到的圖。聯(lián)圖K1∨Cn稱為輪形圖，聯(lián)圖K1∨Pn稱為扇形圖。其它涉及到的概念和定義可參見文獻[1]。

Randic[2]在1979年提出圖 G的解析（Dissection）的這一圖的化學(xué)指標(biāo)的概念，可以用來描述有機物的分子結(jié)構(gòu)，和其他化學(xué)指標(biāo)有著密切的聯(lián)系[3-4]。它是一個關(guān)于圖G的二元向量(a,b)，記圖G的解析為 D(G)=(a(G),b(G))，在文獻[3,5]中有如下遞歸定義：

1)若 G=K1，則 D(G)=(1,0)；

2)若 G=K2,則 D(G)=(1,0)；

由此遞歸定義，在文獻[6]中，有如下關(guān)于圖的解析的另一種計算方法。

設(shè)G為一個至少有三個頂點的連通圖，V(G)={v1,v2,…,vn}，對于給定 v∈V(G)，在 V(G){v}中的頂點序列vi1vi2…vik若滿足

1)在G-vi1-vi2-…-vik-1中包含v的連通分支至少有三個頂點；

2)在G-vi1-vi2-…-vik中v是孤立點；

3)對每個 j∈(2,3,…,k)，v 和 vij都在 G-vi1-vi2-…-vij-1的同一個連通分支中。則稱序列vi1vi2…vik為相對于頂點v的一個鏈。圖G中相對于v的鏈的數(shù)目記為a(G,v)。

對于給定邊 e=vivj∈E(G)，在 V(G){vi,vj}中的頂點序列vi1vi2…vik滿足

1)在G-vi1-vi2-…-vik-1中包含e的連通分支至少有三個頂點；

2)在G-vi1-vi2-…-vik中e是孤立邊；

3)對每個 j∈(2,3,…,k)，e 和 vij都在 G-vi1-vi2-…-vij-1的同一個連通分支中。則稱序列vi1vi2…vik為相對于邊e的一個鏈。圖G中相對于e的鏈的數(shù)目記為b(G,e)。

定理1[6]設(shè)G是一個至少有4個頂點的連通圖，則有

在文獻[5]中給出一些關(guān)于圖的解析的基本性質(zhì)，并給出一些常見圖的解析值。

命題1[5]設(shè)n為一個正整數(shù)，則有

在文獻[7]中給出樹圖的解析的上下界，圖的解析的性質(zhì)研究參見文獻[5,8]。由其定義，可知道圖的解析的計算是一個NP問題，本文結(jié)合圖的解析兩種計算方法，給出輪形圖（圖1）和扇形圖（圖2）的解析值。

2 主要結(jié)論

定理2設(shè)圖G為輪形圖K1∨Cn，n≥5,則有

當(dāng) n=3，4 時，易計算得 D(K1∨C3)=D(K4)=(0,12)，D(K1∨C4)=(24,48)；D(K1∨P3)=(4,10)。

3定理的證明

3.1 定理2的證明

首先利用定理1來計算a(G)。如圖1，輪形圖G的中心點v0與圈中所有點都相連，所以去掉圈上的點，最后包含v0的子圖要么是C3要么是P3（此時v0為中間頂點），所以相對于中心點v0的鏈的數(shù)目a(G,v0)。由對稱性，圈上所有頂點的鏈的數(shù)目都相等?，F(xiàn)取v為圈上一個頂點，設(shè)在關(guān)于頂點v的鏈中v0排在第m位，由于頂點v的每一個鏈必含有v0，故現(xiàn)對m進行分類來計算G中相對于v的鏈的數(shù)目。

1)m=1中心點v0在鏈的第一位，即首先去掉v0剩余是Cn。在Cn中相對于每個點的鏈數(shù)目是相等的，由命題 1，得所以m=1時，G中相對于v的鏈的數(shù)目為2×3n-4。

2)m=2中心點v0在鏈的第2位，即先去掉圈中除v外的一個頂點，再去掉中心點v0時，得到含v的一條路Pn-1。當(dāng)鏈中第一個頂點取V(Cn){v}中不同點時，可得到頂點v位于長度為n-1的所有不同位置的路Pn-1由命題1，得中心點v0在第2位的鏈的數(shù)目為a(Pn-1)=2×3n-4。

3)3≤m≤n-2,中心點v0在鏈的第m位，即前面已去掉圈中的m-1個點。當(dāng)這個m-1頂點的導(dǎo)出子圖是一條路（也即這m-1個頂點在Cn中按一定次序依次相連）時，去掉中心點v0后，剩余的子圖為包含v的路Pn-m+1。而且這相鄰的

4)m=n-1中心點v0在鏈的第n-1位，即前面已去掉Cn中的n-2個頂點，剩余子圖要么為含v和v0的C3要么是含v和v0的P3。當(dāng)是C3時，由D(C3)=(0,3)，故這樣的鏈的數(shù)目為0；當(dāng)是P3時，與v0關(guān)聯(lián)的另外一個頂點是在除了頂點v在圈上的兩個臨點外的頂點，故這樣的鏈的數(shù)目為(n-2)!(n-3)。

5)m=n按這樣的頂點序列順序去掉頂點，最后剩余的子圖為含v的一條邊，故對a(G,v)的貢獻為零。

對于b(G)，應(yīng)用定理1，將輪形圖G的邊分為兩類 E1和E2，其中 E1={vivo|i=1,2,…,n}，E2={vivj|vivj∈E(G),i,j=1,2,…,n}。若 e∈E1，則圖G中相對于邊e的鏈是由除去邊e的兩個端點，剩余n-1個頂點的任意排列，即b(G,e)=(n-1)!。若e∈E2，類似計算a(G)的分析，同理得到

至此定理2得證。

3.2 定理3的證明

[1]BONDY J A,MURTY U S R.Graph theory with applications[M].Macmillan,London and Elsevier,New York,1976.

[2]RANDIC M.On dissection of acyclic graphs[J].MATCH Commun Math Comput Chem,1979,5:135-148.

[3]RANDIC M,GUO X F,CALKINS P.Graph dissetion revisited:application to smaller alikanes[J].Acta Chim Slov,2000,47:489-506.

[4]RANDIC M,WOODWORTH W L.Characterization of acyclic graphs by successive dissection[J].MATCH Commun Math Comput Chem,1982,13:291-313.

[5]XU Z X,WU B,GUO X F.On dissection of graphs[J].MATCH Commun Math Comput Chem,2006,56:519-526.

[6]段 芳,王 曉.A New method in computing the dissection of some graphs[J].新疆大學(xué)學(xué)報:自然科學(xué)版，2008，25(3)：293-297.

[7]王 曉,段 芳.On dissection of unicyclic graphs[J].華東師范大學(xué)學(xué)報,2009,1(143):13-21.

[8]張 莉.樹的剖分值[J].應(yīng)用數(shù)學(xué)學(xué)報,2008(31):852-860.