四面體圖與完全圖字典積的平均首達(dá)時(shí)間

倪 琦，周 環(huán)，呂寧寧，潘向峰

(1.安徽大學(xué) 數(shù)學(xué)科學(xué)學(xué)院,合肥 230601；2.安徽工業(yè)經(jīng)濟(jì)職業(yè)技術(shù)學(xué)院公共教學(xué)部，合肥 230051)

平均首達(dá)時(shí)間是有限隨機(jī)游走的重要性質(zhì)參數(shù)之一,被廣泛用于各種網(wǎng)絡(luò)的動(dòng)態(tài)研究,國(guó)內(nèi)外學(xué)者致力于研究其數(shù)值計(jì)算和理論表達(dá)式。[1]陳海燕[2]等通過多項(xiàng)式方法推導(dǎo)出了強(qiáng)連通非周期有向圖上隨機(jī)游走的平均首達(dá)時(shí)間的表達(dá)式,并利用這個(gè)新的公式給出了強(qiáng)正則圖與完全圖的二元運(yùn)算(弱直積、直積、卡氏積)生成圖上的平均首達(dá)時(shí)間。文獻(xiàn)[3]和[4]分別給出了Johnson 圖J(n,3)的特征值與相應(yīng)的特征重?cái)?shù)。王志俊[5]等確定了圖G 與連通正則圖H 的字典積圖的特征多項(xiàng)式和鄰接譜。倪湘鈞[6]等研究了強(qiáng)正則圖與完全圖的字典積的平均首達(dá)時(shí)間。圖的字典積是一種二進(jìn)制運(yùn)算，它可以從舊圖生成新圖。與笛卡爾積和圖的強(qiáng)積等其他二元運(yùn)算不同,圖的字典積不滿足交換律,其特征多項(xiàng)式一般不能由兩個(gè)組成圖的特征多項(xiàng)式確定。[5]

受到上述文獻(xiàn)的啟發(fā),基于連通的強(qiáng)正則圖是直徑為2 的一類距離正則圖這一事實(shí),本文繼續(xù)深入研究直徑為3的一類距離正則圖Johnson圖J(n,3)與完全圖字典積的平均首達(dá)時(shí)間和電阻距離以及度積基爾霍夫指數(shù)、凱梅尼常數(shù)等圖不變量。文獻(xiàn)[7]闡述了基爾霍夫指數(shù)近年來的研究情況。這里只討論無(wú)向的簡(jiǎn)單連通圖,如無(wú)特殊說明將遵循文獻(xiàn)[8]中的符號(hào)和術(shù)語(yǔ)。

1 預(yù)備知識(shí)

定義1[9]Johnson 圖J(n,m)定義如下:其中n是N元集合N={1,2,3,…,n}的元素個(gè)數(shù),頂點(diǎn)集V(J(n,m))由N 的m元子集構(gòu)成,顯然圖中有個(gè)點(diǎn),其中任意兩點(diǎn)相鄰當(dāng)且僅當(dāng)它們中僅有一個(gè)元素不同。……