摘要： 設(shè)路Pm與星圖S1，n-1的強乘積圖為G=PmS1，n

-1. 首先， 通過歸納假設(shè)和構(gòu)造內(nèi)點或邊不交路的方法， 結(jié)合星圖的中心性， 給出圖G的點容錯直徑Dw（G）和邊容錯直徑D′t（G）. 結(jié)果表明， 對圖G中

發(fā)生的任意點或邊故障， 都有Dw（G）≤d（G）+2， D′t（G）≤d（G）+1. 其次， 通過頂點數(shù)和邊數(shù)構(gòu)造的不等關(guān)系， 給出兩個極大連通圖的強乘積圖的

點容錯直徑的上界， 以及兩個非平凡連通圖的強乘積圖的邊容錯直徑的上界.

關(guān)鍵詞： 路； 星圖； 強乘積圖； 點容錯直徑； 邊容錯直徑

中圖分類號： O157.5" 文獻標(biāo)志碼： A" 文章編號： 1671-5489（2024）03-0487-10

Fault Diameter of Strong Product Graph of Path and Star Graph

YUE Yuxiang1，2，3， LI Feng1

（1. College of Computer， Qinghai Normal University， Xining 810008， China；2. The State Key Laboratory of Tibetan Intelligent Information

Processing and Application， Xining 810008， China；

3. College of Information Engineering， Xinyang Vocational College of Art， Xinyang 464007， Henan Province， China）

Abstract： Let the strong product graph of path Pm and star graph S1，n-1 be G=Pm

S1，n-1. Firstly， by inducing assumptions and constructing internally vertex or edge disjoint paths， combined with the centrality of

star graph， the vertex fault diameter Dw（G） and edge fault diameter D′t（G） of the graph G were given. The results show that for a

ny vertex or edge fault in the graph G， there holds Dw（G）≤d（G）+2 and D′t（G）≤d（G）+1. Secondly， through the unequal relation between the

number of vertices and the number of edges， the upper bound of the vertex fault diameter of the strong product graph of two maximally connected graphs and the

upper bound of the edge fault diameter of the strong product graph of two nontrivial connected graph were given.

Keywords： path; star graph; strong product graph; vertex fault diameter; edge fault diameter

收稿日期： 2023-04-17.

第一作者簡介： 岳宇翔（1994—）， 男， 漢族， 碩士， 從事組合網(wǎng)絡(luò)理論及優(yōu)化的研究， E

-mail： yueyuxiang21@126.com. 通信作者簡介： 李" 峰（1981—）， 男， 漢族， 博士， 教授， 從事圖與網(wǎng)絡(luò)優(yōu)化設(shè)計的研究， E-mail： li2006369@126.com.

基金項目： 國家自然科學(xué)基金（批準(zhǔn)號： 11551002）和青海省自然科學(xué)基金（批準(zhǔn)號： 2019-ZJ-2093）.

1" 引言與預(yù)備知識

強乘積的概念最早由Sabidussi［1］提出， 是一種高效由小圖構(gòu)造大圖的圖乘積方法， 并且構(gòu)造出的強乘積圖保留了許多子圖所具有的理想屬性. 目前， 關(guān)于強乘積圖的研究已有很多結(jié)果［1-8］.

Sun等［3］首先給出了任意兩個連通圖的強乘積圖的連通度下界; Yang等［4］在文獻［3］的基礎(chǔ)上對其下界進行改善， 確定了

兩個極大連通圖的強乘積圖的連通度與兩個非平凡連通圖的強乘積圖的邊連通度； pacapan［5］確定了兩個任意連通圖的強乘積圖的連通度.

除強乘積外， 圖乘積領(lǐng)域?qū)ζ渌朔e的研究也取得了很多結(jié)果， 主要涉及可遷性和嵌入等［9-11］.

容錯直徑是Krishnamoorthy等［12］提出用于衡量網(wǎng)絡(luò)發(fā)生故障后， 對整個網(wǎng)絡(luò)信息傳輸效率影響的概念. 但由于故障的隨機性， 確定實際網(wǎng)

絡(luò)中的容錯直徑仍很困難. 文獻［13-14］給出了連通圖的點容錯直徑與邊容錯直徑的上界； 文獻［15］得到了點容錯直徑與邊容錯直徑之間的關(guān)系. 對一些著名網(wǎng)絡(luò)， 其

容錯直徑的值能通過特定的構(gòu)造方法被確定. Esfahanian等［16］首先得到了無向de Brujin網(wǎng)絡(luò)的點容錯直徑； Krishnamoorthy等

［12］給出了超立方體、 立方連通圈和Petersen圖的點容錯直徑， Latifi［17］得到了星圖的點容錯直徑； Du等［18］確

定了有向Kautz網(wǎng)絡(luò)的點容錯直徑； Chen［19］給出了超立方體網(wǎng)絡(luò)的邊容錯直徑. 最近關(guān)于容錯直徑的研究主要集中在變形超立方體網(wǎng)絡(luò)上， Ma等

［20］給出了增強超立方體的點容錯直徑， Qi等［21］給出了扭曲超立方體的點容錯直徑.

圖乘積作為一種重要的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)構(gòu)造方法， 對乘積圖容錯直徑的研究備受關(guān)注， 但目前大部分結(jié)論都是關(guān)于笛卡爾乘積圖的容錯直徑［22-23］， 對強乘積圖

容錯直徑的研究報道較少. 為進一步拓展乘積圖容錯直徑的研究， 并尋找新的具有高可靠性的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)， 本文研究強乘積圖的容錯直徑. 首先， 通過歸納假設(shè)

和構(gòu)造內(nèi)點或邊不交路的方法， 結(jié)合星圖的中心性， 給出路與星圖的強乘積圖的點容錯直徑和邊容錯直徑. 其次， 通過頂點數(shù)和邊數(shù)構(gòu)造的不等關(guān)系， 給出兩個極大連通圖的強乘

積圖的點容錯直徑的上界， 以及兩個非平凡連通圖的強乘積圖的邊容錯直徑的上界.

設(shè)G=（V（G），E（G））是簡單無向圖， 其中V（G）是頂點集， E（G）是邊集. 設(shè)R是圖G中的一條路徑， 其頂點集為V（R）， 則路徑R的長度為V（R）-1， 表示為L（R）. 令x和y是圖G中兩個不同的頂點， 用（x，y）表示圖

G中連接x和y的邊. 圖G中x和y之間的最短路長度為x與y之間的距離， 記為d（G;x，y）. 圖G的直徑即為在圖G中任意兩個頂點之間的最大距離， 記為d（G）. 如果連接x和y有兩條及以上的路徑， 且除端點x和端

點y外， 這些路內(nèi)部頂點都不相同， 則稱這些路是內(nèi)點不交的. 圖G中x和y之間的內(nèi)點不交路的最大條數(shù)記為ζ（G;x，y）. 如果連接x和y有兩條及以

上的路徑， 且這些路中所有邊都不相同， 則稱這些路是邊不交的. 圖G中x和y之間的邊不交路的最大條數(shù)記為η（G;x，y）.

僅含有一個頂點的圖稱為平凡圖. 若在圖G中刪除一部分頂點子集或邊子集， 使得被刪除后的圖G成為非連通圖或者平凡圖， 則稱該子集為圖G的頂點分離集或邊分

離集. 圖的連通度指圖G中最小頂點分離集的基數(shù)， 記為κ（G）. 若存在正整數(shù)k使得κ（G）≥k， 則稱圖G為k-連通的. 同理， 圖的邊連通度是指圖G中最小邊分離集的基數(shù)， 記為λ（G）. 若存在正整數(shù)k使得λ（G）≥k，

則稱圖G為k-邊連通的. 圖G的最小度表示為δ（G）. 如果一個連通圖G滿足κ（G）=δ（G）， 則圖G稱為極大連通圖. 本文討論的路和星圖都是極大連通圖.

強乘積是廣泛使用的一種圖乘積運算， 下面給出強乘積的定義及相關(guān)性質(zhì).

定義1" 令G1=（V（G1），E（G1））和G2=（V（G2），E（G2））是任意兩個連通圖， 則將G1和G2的強乘積記為G1G2， 定義其頂點集為V（G

1）×V（G2）. 若任意兩個不同的頂點x1y1和x2y2在G1G2中相鄰， 則當(dāng)且僅當(dāng)x1=x2且（y1，y2）∈E（G2）或者y1=y2且（x1，

x2）∈E（G1）或者（x1，x2）∈E（G1）且（y1，y2）∈E（G2）.

根據(jù)強乘積的定義及文獻［1］的結(jié)論知， 對任意兩個連通圖G1和G2， 其強乘積G=G1G2是可交換的、 可結(jié)合的：

G1G1G2G1，

G1（G2G3）（G1G2）G3.

強乘積G的頂點數(shù)為

V（G）=V（G1）V（G2），

強乘積G的邊數(shù)為

E（G）=V（G1）E（G2）+V（G2）E（G1）+2E（G1）E（G2），

強乘積G的最小度為

δ（G）=δ（G1）+δ（G2）+δ（G1）δ（G2）.

將m階路與n階星圖的強乘積圖表示為G=PmS1，n-1， 在強乘積圖G中有4類頂點， 分別為3度點、 5度點， （2n-1）度點和（3n-1）度點.

易知（3n-1）度點是圖G中的最大度頂點， 仍然與同層頂點和上下層頂點鄰接， 起到中心控制的作用. 3度點是圖G中的最小度頂點， 考慮圖G的容錯直徑基于這類頂點. 若令xayu和

xbyv是G中任意不同兩個頂點， 且xa，xb∈V（Pm）， yu，yv∈V（S1，n-1）， 則xayu和xbyv鄰接當(dāng)且僅當(dāng)xa=xb且yu

和yv中至少有一個中心點或yu=yv且b-a=1或b-a=1且yu和yv中至少有一個中心點. 圖1為3階路與4階星圖的強乘積圖P3

S1，3， 其中標(biāo)注了4類頂點在圖中的位置.

圖1" 強乘積圖P3S1，3

Fig.1" Strong product graph P3S1，3

容錯直徑根據(jù)點故障或邊故障的不同情形可分為點容錯直徑和邊容錯直徑.

定義2［24］" 令G是一個w-連通圖， 定義G的故障點集為F， 且Flt;w， 則圖G的（w-1）-點容錯直徑定義為

Dw（G）=max{d（G-F）： FV（G）， Flt;w}.

在最差情況下， 只討論F=w-1的情形. 所以對任何的w-連通圖G， 直徑和點容錯直徑都滿足

d（G）=D1（G）≤D2（G）≤…≤Dw-1（G）≤Dw（G）.

定義3［24］" 令G是一個t-邊連通圖， 定義G的故障邊集為F， 且Flt;t， 則圖G的（t-1）-邊容錯直徑定義為

D′t（G）=max{d（G-F）： FE（G）， Flt;t}.

在最差情況下， 只討論F=t-1的情形. 所以對任何的t-邊連通圖G， 直徑和邊容錯直徑的關(guān)系均為

d（G）=D′1（G）≤D′2（G）≤…≤D′t-1（G）≤D′t（G）.

2" 主要結(jié)果

引理1［4］" 設(shè)G1和G2是兩個極大連通圖， G1的階數(shù)為n1， G2的階數(shù)為n2， 則G1和G2的強乘積圖的連通度為

κ（G1G2）=min{δ1n2，δ2n1，δ1+δ2+δ1δ2}.（1）

推論1" 設(shè)G=PmS1，n-1是Pm和S1，n-1的強乘積圖， Pm和S1，n-1分別是m（≥2）階路和n（≥3）階星圖， 則G

的連通度為

κ（G）=2，m=2，3，m≥3.（2）

證明： 由于δ（Pm）=δ（S1，n-1）=1， 故根據(jù)引理1可得κ（G）=min{n，m，3}. 根據(jù)m值的分類有以下兩種情形.

情形1） m=2. 此時有mlt;n和mlt;3， 故有κ（G）=2.

情形2） m≥3. 此時有3≤m且3≤n， 故有κ（G）=3. 證畢.

引理2［2］" 設(shè)G1和G2是兩個任意連通圖， xayu和xbyv是G1和G2的強乘積圖G=G1G2中任意兩個不同頂點， 且有xa，xb∈V（G1）和yu，yv∈V（G2）， 則在圖G中頂點xayu和頂點xbyv之間的距離為

d（G;xayu，xbyv）=max{d（G1;xa，xb），d（G2;yu，yv）}.（3）

推論2" 設(shè)G=PmS1，n-1是Pm和S1，n-1的強乘積圖， Pm和S1，n-1分別是m（≥2）階路和n（≥3）階星圖， 則G的直徑為

d（G）=2，m=2，m-1，m≥3.（4）

證明： 令路Pm的頂點集為V（Pm）={x1，x2，…，xm}， 星圖S1，n-1的頂點集為V（S1，n-1）={y1，y2，…，yn}. 令xayu和xby

v是G中任意不同兩個頂點， 且xa，xb∈V（Pm）， yu，yv∈V（S1，n-1）. 若m=2， 則G=P2S1，n-1， 易得此時圖

G的直徑為d（G）=2. 若m≥3， 則由引理2可得

d（G;xayu，xbyv）=max{d（Pm;xa，xb），d（S1，n-1;yu，yv）}≤max{m-1，2}=m-1.（5）

當(dāng)a=1且b=m時， d（G;xayu，xbyv）=m-1， 式（5）的不等式可取等號. 又因為d（G）是在圖G中任意兩個頂點之間的最大距離， 故可得此時圖G的直徑為d（G）=m-1. 證畢.

定理1" 設(shè)G=PmS1，n-1是Pm和S1，n-1的強乘積圖， Pm和S1，n-1分別是m（≥2）階路和n（≥3）階星圖， 則對任何1

≤w≤3， 圖G的點容錯直徑為

Dw（G）=d（G）+1，w=2，d（G）+2，w=3.（6）

證明： 令路Pm的頂點集為V（Pm）={x1，x2，…，xm}， 星圖S1，n-1的頂點集為V（S1，n-1）={y1，y2，…，yn}. 令xayu和xby

v是G中任意不同兩個頂點， 且xa，xb∈V（Pm）， yu，yv∈V（S1，n-1）. 不失一般性， 不妨設(shè)a≤b， u≤v， 星圖S1

，n-1的中心點為y1. 因為星圖S1，n-1的階數(shù)最少為3， 故如果yu和yv中有一個頂點是中心點， 則不妨設(shè)星圖S1，n-1中至少還存在頂點

y2. 如果yu和yv都是中心點， 則不妨設(shè)星圖S1，n-1中至少還存在頂點y2和頂點y3. 此外， 在證明過程中還將列舉出相鄰兩點的內(nèi)點不交路， 這是為方便后續(xù)結(jié)果轉(zhuǎn)化為邊不交路的情形.

情形1） m=2.

不失一般性， 不妨設(shè)V（Pm）{xa，xb}. 由推論1和推論2可知， 此情形下圖G的連通度為2， 直徑為2.

① xa=xb. 此時， 若yu和yv中有一個頂點是中心點， 不妨設(shè)yu=y1， 則在圖G中頂點xay1和頂點xayv之間構(gòu)造2條內(nèi)點不交路：

R1： xay1→xby1→xayv，R2： xay1→xbyv→xayv，（7）

這2條內(nèi)點不交路的長度為2=d（G）. 若yu和yv都不是中心點， 則在圖G中頂點xayu和頂點xayv之間構(gòu)造2條內(nèi)點不交路：

R3： xayu→xay1→xayv，R4： xayu→xby1→xayv，（8）

這2條內(nèi)點不交路的長度為2=d（G）.

② yu=yv. 此時， 若yu和yv都是中心點， 則在圖G中頂點xay1和頂點xby1之間構(gòu)造2條內(nèi)點不交路：

R5： xay1→xby2→xby1，R6： xay1→xby3→xby1，（9）

這2條內(nèi)點不交路的長度為2=d（G）. 若yu和yv都不是中心點， 則在圖G中頂點xayu和頂點xbyu之間構(gòu)造2條內(nèi)點不交路：

R7： xayu→xby1→xbyu，R8： xayu→xay1→xbyu，（10）

這2條內(nèi)點不交路的長度為2=d（G）.

③ xa≠xb且yu≠yv. 此時， 若yu和yv中有一個頂點是中心點， 不妨設(shè)yu=y1， 則在圖G中頂點xay1和頂點xbyv之間構(gòu)造2條內(nèi)點不交路：

R9： xay1→xby1→xbyv，R10： xay1→xayv→xbyv，（11）

這2條內(nèi)點不交路的長度為2=d（G）. 若yu和yv都不是中心點， 則在圖G中頂點xayu和頂點xbyv之間構(gòu)造2條內(nèi)點不交路：

R11： xayu→xby1→xbyv，R12： xayu→xay1→xbyv，（12）

這2條內(nèi)點不交路的長度為2=d（G）.

綜上可知在此情形下， 圖G中任意兩個頂點之間至少存在2條長度不超過d（G）的內(nèi)點不交路， 故對任意的1≤w≤2， 都有Dw（G）=d（G）.

情形2） mgt;3.

同理可得此情形下圖G的連通度為3和直徑d（G）≥3. 根據(jù)頂點xayu和頂點xbyv的位置關(guān)系有以下3種情形.

① xa=xb.

當(dāng)w=3， F=2時， 若yu和yv都不是中心點， 則若a=1或n， 不妨設(shè)a=1， 在圖G中頂點x1yu和頂點x1yv之間構(gòu)造3條內(nèi)點不交路：

R13： x1yu→x1y1→x1yv，R14： x1yu→x2y1→

x1yv，R15： x1yu→x2yu→x3y1→x2yv→x1yv，（13）

這3條內(nèi)點不交路的長度不超過4≤d（G）+1. 若1lt;alt;n， 則在圖G中頂點xayu和頂點xayv之間構(gòu)造3條內(nèi)點不交路：

R16： xayu→xay1→xayv，R17： xayu→xa-1y1→xayv，R18： xayu→xa+1y1→xayv，（14）

這3條內(nèi)點不交路的長度不超過2lt;d（G）.

當(dāng)w=2， F=1時， 則在以上情形中， 圖G中頂點xayu和頂點xayv之間可構(gòu)造2條長度不超過2lt;d（G）的內(nèi)點不交路R13和R14.

當(dāng)w=3， F=2時， 若yu和yv中有一個頂點是中心點， 不妨設(shè)yu=y1， 則若a=1或n， 不妨設(shè)a=1， 在圖G中頂點x1y1和頂點x1yv之間構(gòu)造3條內(nèi)點不交路：

R19： x1y1→x1yv，R20： x1y1→x2y1→x1yv，R21： x1y

1→x2yv→x1yv，（15）

這3條內(nèi)點不交路的長度不超過2lt;d（G）. 若1lt;alt;n， 則在圖G中頂點xay1和頂點xayv之間構(gòu)造3條內(nèi)點不交路：

R22： xay1→xayv，R23： xay1→xa-1y1→xayv，R24

： xay1→xa+1y1→xayv，（16）

這3條內(nèi)點不交路的長度不超過2lt;d（G）.

當(dāng)w=2， F=1時， 則在以上情形中， 顯然圖G中頂點xayu和頂點xayv之間也可構(gòu)造2條長度不超過2lt;d（G）的內(nèi)點不交路.

② yu=yv.

當(dāng)w=3， F=2時， 若yu和yv都不是中心點， 且u≠2， 則在圖G中頂點xayu和頂點xbyu之間構(gòu)造3條內(nèi)點不交路：

R25： xayu→…→xbyu，R26： xayu→xa+1y1→

xa+2y2→…→xb-1y2→xby1→xbyu，R27： xayu

→xay1→xa+1y2→xa+2y1→…→xb-1y1→xbyu，（17）

這3條內(nèi)點不交路的長度不超過b-a+1≤d（G）+1. 若yu和yv都是中心點， 則在圖G中頂點xay1和頂點xby1之間構(gòu)造3條內(nèi)點不交路：

R28： xay1→…→xby1，R29： xay1→xa+1y2→

…→xb-1y2→xby1，R30： xay1→xa+1y3→…→xb-1y3→xby1，（18）

這3條內(nèi)點不交路的長度不超過b-a≤d（G）.

當(dāng)w=2， F=1時， 若yu和yv都不是中心點， 則只需將R29中的y1用yu替代， y2用y1替代， 結(jié)合R25， 即可得到

在圖G中頂點xayu和頂點xbyu之間的2條長度不超過b-a≤d（G）的內(nèi)點不交路. 若yu和yv都是中心點， 則在圖G中頂點xay1

和頂點xby1之間可構(gòu)造2條長度不超過b-a≤d（G）的內(nèi)點不交路R28和R29.

綜上可得此情形下滿足D2（G）≤d（G）.

③ xa≠xb且yu≠yv.

當(dāng)w=3， F=2時， 若yu和yv都不是中心點， 則在圖G中頂點xayu和頂點xbyv之間構(gòu)造3條內(nèi)點不交路：

R31： xayu→xa+1y1→…→xb-1y1→xbyv，

R32： xayu→…→xb-1yu→xby1→xbyv，R33： xayu→xay1→xa+1yv→…→xbyv，（19）

這3條內(nèi)點不交路的長度不超過b-a+1≤d（G）+1. 若yu和yv中有一個頂點是中心點， 不妨設(shè)yu=y1， 且v≠2， 則在圖G中頂點xay1和頂點xbyv之間構(gòu)造3條內(nèi)點不交路：

R34： xay1→xa+1yv→…→xbyv，R35： xay1→

…→xb-1y1→xbyv，R36： xay1→xa+1y2→…→xb-1y2→xby1→xbyv，（20）

這3條內(nèi)點不交路的長度不超過b-a+1≤d（G）+1.

當(dāng)w=2， F=1時， 若yu和yv都不是中心點， 則只需將R32中的xb-1yu用xb-2yu替代及xby1用xb-1y

1替代， 將R33中的xay1用xa+1y1替代及xa+1yv用xa+2yv替代， 即可得到在圖G中頂點xayu和頂點xby

v之間的2條長度不超過b-a≤d（G）的內(nèi)點不交路. 若yu和yv中有一個頂點是中心點， 則在圖G中頂點xay1和頂點xbyv之間可構(gòu)

造2條長度不超過b-a≤d（G）的內(nèi)點不交路R34和R35.

綜上分析可得D2（G）=d（G），" D3（G）≤d（G）+1.

下面討論下界， 考慮圖G中的兩個頂點x1y2和xmy2. 若未發(fā)生故障， 則圖G中兩點

之間的距離為d（G;x1y2，xmy2）=d（G）. 若令故障點集F={x2y1，x2y2}， 則在G-F中頂點x1y2和xmy2之間的距離為

d（G-F;x1y2，xmy2）=d（G）+1，

故可得D3（G）≥d（G）+1.

情形3） m=3.

此情形下圖G的連通度為3， 直徑為2. 當(dāng)w=2， F=1時， 由情形2）易得此情形下D2（G）≤d（G）+1， 若令故障點集F={x2y1}， 則在G-F中

頂點x1y2和x3y3之間的距離為

d（G-F;x1y2，x3y3）=3=d（G）+1，

故可得D2（G）≥d（G）+1. 當(dāng)w=3， F=2時， 構(gòu)造內(nèi)點不交路的方法如情

形2）， 但由于直徑不同， 式（13）中的R15長度變?yōu)?≤d（G）+2， 于是可得D3（G）≤d（G）+2. 若令故障點集F={x1y1，x2y1}， 則

在G-F中頂點x1y2和x1y3之間的距離為d（G-F;x1y2，x1y3）=4=d（G）+2，

故可得D3（G）≥d（G）+2. 證畢.

引理3［5］" 設(shè)G1和G2是非平凡連通圖， G1和G2的階數(shù)分別為n1和n2， G1和G2的邊數(shù)分別為c1和c2， 則G1和G2的強乘積圖邊連通度為

λ（G1G2）=min{λ1（n2+2c2），λ2（n1+2c1），δ1+δ2+δ1δ2}.（21）

推論3" 設(shè)G=PmS1，n-1是Pm和S1，n-

1的強乘積圖， Pm和S1，n-1分別是m（≥2）階路和n（≥3）階星圖， 則G的邊連通度為

λ（G）=3.（22）

證明： 因為λ（Pm）=λ（S1，n-1）=1， 故由引理3可得λ（G）=min{3n-2，3m-2，3}. 又因為3n-2≥7且3m-2≥4， 故得λ（G）=3. 證畢.

定理2" 設(shè)G=PmS1，n-1是Pm和S1，n-1的強乘積圖，

Pm和S1，n-1分別是m（≥2）階路和n（≥3）階星圖， 則對任何2≤t≤3， G的邊容錯直徑為

D′t（G）=d（G）+1.（23）

證明： 設(shè)路Pm的頂點集為V（Pm）={x1，x2，…，xm}， 星圖S1，n-1的頂點集為V（S1，n-1）={y1，y2，…，yn}. 令xayu和xby

v是G中任意不同兩個頂點， 且xa，xb∈V（Pm）， yu，yv∈V（S1，n-1）. 不失一般性， 不妨設(shè)alt;b， ult;v， 設(shè)星圖S1，n-1的中

心點為y1. 若yu和yv中有一個頂點是中心點， 則設(shè)星圖S1，n-1中至少存在中心點y1、 頂點y2和頂點yu或yv. 若yu和

yv都是中心點， 則設(shè)星圖S1，n-1中至少存在中心點y1、 頂點y2和頂點y3.

情形1） m=2.

不失一般性， 令路Pm的頂點集為V（Pm）={xa，xb}. 由推論2和推論3可知在此情形下， 圖G的直徑為2， 邊連通度為3.

① xa=xb.

若yu和yv都不是中心點， 則在圖G中頂點xayu和頂點xayv之間構(gòu)造3條邊不交路：

R′1： xayu→xay1→xayv，R′2： xayu→xbyu→

xby1→xayv，R′3： xayu→xby1→xbyv→xayv，（24）

這3條邊不交路的長度不超過3=d（G）+1. 若yu和yv中有一個頂點是中心點， 不妨設(shè)yu=y1， 則在圖G中頂點xay1和頂點xayv之間構(gòu)造3條邊不交路：

R′4： xay1→xayv，R′5： x

ay1→xby1→xayv，R′6： xay1→xbyv→xayv，（25）

這3條邊不交路的長度不超過2=d（G）.

② yu=yv.

若yu和yv都不是中心點， 則在圖G中頂點xayu和頂點xbyu之間構(gòu)造3條邊不交路：

R′7： xayu→xbyu，R′8： x

ayu→xay1→xbyu，R′9： xayu→xby1→xbyu，（26）

這3條邊不交路的長度不超過2=d（G）. 若yu和yv都是中心點， 則可在圖G中頂點xay1和頂點xby1之間構(gòu)造3條邊不交路：

R′10： xay1→xby1，R′11

： xay1→xby2→xby1，R′12： xay1→xby3→xby1，（27）

這3條邊不交路的長度不超過2=d（G）.

③ xa≠xb且yu≠yv.

若yu和yv都不是中心點， 則在圖G中頂點xayu和頂點xbyv之間構(gòu)造3條邊不交路：

R′13： xayu→xay1→xbyv，R′14： xayu→xby

1→xayv→xbyv，R′15： xayu→xbyu→xby1→xbyv，（28）

這3條邊不交路的長度不超過3=d（G）+1. 若yu和yv中有一個頂點是中心點， 不妨設(shè)yu=y1， 則在圖G中頂點xay1和頂點xbyv之間構(gòu)造3條邊不交路：

R′16： xay1→xbyv，R′17

： xay1→xby1→xbyv，R′18： xay1→xayv→xbyv，（29）

這3條邊不交路的長度不超過2=d（G）.

在此情形下， D′3（G）≤d（G）+1. 考慮圖G中的兩個頂點x1y2和x2y3. 若令故障邊集F={（x1y2，x1y1），（x1y2，x2y1）}， 則

在G-F中頂點x1y2和x2y3之間的距離為

d（G-F;x1y2，x2y3）=3=d（G）+1，

易驗證這也是G-F的直徑， 故可得D′3（G）≥d（G）+

1. 因為內(nèi)點不交也是邊不交， 故由定理1中的情形1）可得D′2（G）=d（G）.

情形2） mgt;3.

由定理1中情形2）可得此情形下， 圖G中任意兩個頂點之間都至少存在2條長度不超過d（G）的邊不交路或3條長度不超過d（G）+1的邊不交路， 則可得

D′3（G）≤d（G）+1， D′2（G）=d（G）.

下面討論下界， 考慮圖G中的兩個頂點x1y2和xmy3. 若令故障邊集F={（x1y2，x2y2），（x1y2，x2y1）}， 則在G-F中頂點x1y2和

xmy3之間的距離為d（G-F;x1y2，xmy3）=d（G）+1， 易驗證這也是G-F的直徑， 故可得D′3（G）≥d（G）+1.

情形3） m=3.

當(dāng)t=2， F=1時， 由定理1中情形2）易得D′2（G）≤d（G）+1， 若令故障邊集F={（x1y2，x2y1）}， 則在G-F中頂點x1y2和

x3y3之間的距離為d（G-F;x1y2，x3y3）=3=d（G）+1，

故可得D′2（G）≥d（G）+1. 當(dāng)t=3， F=2時， 參照定理1中情形2）， 將式（13）中長度

不超過4的3條內(nèi)點不交路R13，R14和R15用式（24）中的3條長度不超過3的邊不交路R′1，R′2和R′3替代， 則可得此情形下， 圖G中任意兩個頂點之間都至少存在3條長度不超過d（G）+1的邊不交

路， 故有D′3（G）≤d（G）+1. 又因為D′3（G）≥D′2（G）≥d（G）+1， 所以可得D′3（G）=d（G）+1. 證畢.

引理4（Menger定理）［24］" 設(shè)G是連通無向圖， x和y是G中不同的兩個頂點， 令κ（G;x，y）表示x與y之間的連通度

， 令λ（G;x，y）表示x與y之間的邊連通度， 則有

ζ（G;x，y）=κ（G;x，y），" （x，y）E（G），η（G;x，y）=λ（G;x，y）.（30）

容錯直徑是一種特殊的直徑， 通過直徑的定義和Menger定理， 再利用故障后的頂點數(shù)與邊數(shù)構(gòu)造的不等關(guān)系， 可給出關(guān)于強乘積圖的點容錯直徑和邊容錯直徑的兩個上界.

定理3" 設(shè)G1和G2是兩個極大連通圖， 階數(shù)分別為n1和n2， 最小度分別為δ1和δ2. 則對任何1≤w≤κ

（G）， G1和G2的強乘積圖G=G1G2的點容錯直徑滿足：

Dw（G）≤maxn1n2-w-1δ1n2-w+1+1，n1n2-w-1δ2n1-w+1+1，n1n2-w-1

δ1+δ2+δ1δ2-w+1+1.（31）

證明： 設(shè)F為故障點集， 且有F=w-1. 不失一般性， 不妨設(shè)d（G-F）=h. 則當(dāng)h≤1時， G-F是完全圖， 從而在G-F中x和y

之間的距離為1. 當(dāng)h≥2時， 設(shè)x和y是G-F中任意兩個不同頂點， 且使得x和y之間的距離為d（G-F;x，y）=h.

由Menger定理可知， 在G-F中x和y之間至少存在（κ（G）-w+1）條內(nèi)點不交路， 且每條路的內(nèi)點數(shù)至少為h-1. 又因為強乘積圖G的頂點數(shù)滿足V（G）=n

1n2， 故可得圖G發(fā)生點故障后， 頂點總數(shù)與x和y之間的內(nèi)點不交路的頂點數(shù)滿足如下關(guān)系：

n1n2-w+1≥（min{δ1n2，δ2n1，δ1+δ2+δ1δ2}-w+1）（h-1）+2，h≤

n1n2-w-1min{δ1n2，δ2n1，δ1+δ2+δ1δ2}-w+1+1=" maxn1n2-w-1δ

1n2-w+1+1，n1n2-w-1δ2n1-w+1+1，

n1n2-w-1δ1+δ2+δ1δ2-w+1+1. （32）

證畢.

定理4" 設(shè)G1和G2是兩個非平凡連通圖， 階數(shù)分別為n1和n2， 邊連通度分別為λ1和λ2， 最小度分別為δ1和δ2

， 邊數(shù)分別為ε1和ε2. 則對任何1≤t≤λ（G）， G1和G2的強乘積圖G=G1G2的邊容錯直徑滿足：

D′t（G）≤maxn1ε2+n2ε1+2

ε1ε2-t+1λ1n2+2λ1ε2-t+1，n1ε2+n2ε1+2ε1ε

2-t+1λ2n1+2λ2ε1-t+1，n1ε2+n2ε1+2ε1

ε2-t+1δ1+δ2+δ1δ2-t+1.（33）

證明： 設(shè)F為故障邊集， 且有F=t-1. 不失一般性， 不妨設(shè)d（G-F）=h. 設(shè)x和y是G-F中任意兩個不同頂點， 且使得x和y之間的距離為d（G-F;x，y）=h.

由Menger定理可知， 在G-F中x和y之間至少存在（λ（G）-t+1）條邊不交路， 且每條路的邊數(shù)至少為h. 又因為強乘積圖G的邊數(shù)滿足

E（G）=n1ε2+n2ε1+2ε1ε2，

故可得圖G發(fā)生邊故障后， 邊總數(shù)與x和y之間的邊不交路的邊數(shù)滿足如下關(guān)系：

n1ε2+n2ε1+2ε1ε2-t+1≥（min{λ1n2+2λ1ε2，λ2n1+2λ2ε1，δ1+δ2+δ1δ2}-t+1）h，

h≤" n1ε2+n2ε1+2ε1ε2-t+1min{λ1n2+2λ1ε2，λ2n1+2λ

2ε1，δ1+δ2+δ1δ2}-t+1=" maxn1ε2+n

2ε1+2ε1ε2-t+1λ1n2+2λ1ε2-t+1，n1ε2+

n2ε1+2ε1ε2-t+1λ2n1+2λ2ε1-t+1，n1ε2+n2ε1+2ε1ε2-t+1δ1+δ2+δ1δ2-t+1.（34）

證畢.

綜上所述， 本文首先通過歸納假設(shè)和構(gòu)造內(nèi)點或邊不交路的方法， 再結(jié)合星圖的中心性， 給出了路與星圖的強乘積圖的點容錯直徑和邊容錯直徑. 結(jié)果表明， 路與星圖的強乘積圖擁有較小

的點容錯直徑和邊容錯直徑， 特別對于邊容錯直徑， 即使在最差邊故障情形下， 其最大傳輸延遲也只有d（G）+1， 是一種適用于高可靠性集中控制系統(tǒng)的拓?fù)浣Y(jié)構(gòu). 其次， 通過頂點

數(shù)和邊數(shù)構(gòu)造的不等關(guān)系， 給出了兩個極大連通圖的強乘積圖的點容錯直徑的上界及兩個非平凡連通圖的強乘積圖的邊容錯直徑的上界， 拓展了關(guān)于強乘積圖的容錯直徑的一般性結(jié)論.

參考文獻

［1］" SABIDUSSI G. Graph Multiplication ［J］. Mathematische Zeitschrift， 1959， 72（1）： 446-457.

［2］" HAMMACK R， IMRICH W， KLAVAR S， et al. Handbook of Product Graphs ［M］. Boca Raton： CRC Press， 2011： 1-533.

［3］" SUN L， XU J M. Connectivity of Strong Product Graphs ［J］. Journal of Univers

ity of Science and Technology of China， 2006， 36（3）： 241-243.

［4］" YANG C， XU J M. Connectivity and Edge-Connectivity of Strong Product Graphs ［

J］. Journal of University of Science and Technology of China， 2008， 38（5）： 449-455.

［5］" PACAPAN S. Connectivity of Strong Products of Graphs ［J］. Graphs and Combinatorics， 2010， 26（3）： 457-467.

［6］" BERMUDO S， HERNNDEZ-GMEZ J C， SIGARRE

TA J M. Total k-Domination in Strong Product Graphs ［J］. Discrete Applied Mathematics， 2019， 263（C）： 51-58.

［7］" GOLOGRANC T， REPOLUSK P. Toll Number of the Strong Product of Graphs ［J］. Discrete Mathematics， 2019， 342（3）： 807-814.

［8］" ANANTHARAMAN S. Adjacent Vertex-Distinguishing Proper Edge-Coloring of Stron

g Product of Graphs ［J］. Applications and Applied Mathematics， 2019， 14（2）： 1169-1187.

［9］" SHARIFI S， IRANMANESH M A. Adjacency and Shift-Transitivity in Graph Product

s ［J］. Iranian Journal of Science and Technology， Transactions A： Science， 2017， 41（3）： 707-711.

［10］" DARA S， MISHRA S， NARAYANAN N， et al. Strong Edge Coloring of Cayley Graphs

and Some Product Graphs ［J］. Graphs and Combinatorics， 2022， 38（2）： 51-1-51-20.

［11］" ZARIBAFIYAN A， MARCHAND D J J， CHANGIZ REZAEI S S. Systematic and Determinis

tic Graph Minor Embedding for Cartesian Products of Graphs ［J］. Quantum Information Processing， 2017， 16（5）： 136-1-136-26.

［12］" KRISHNAMOORTHY M S， KRISHNAMURTHY B. Fault Diameter

of Interconnection Networks ［J］. Computers and Mathematics with Applications， 1987， 13（5/6）： 577-582.

［13］" CHUNG F R K， GAREY M R. Diameter Bounds for Altered Graphs ［J］. Journal of Graph Theory， 1984， 8（4）： 511-534.

［14］" DANKELMANN P. Bounds on the Fault-Diameter of Graphs ［J］. Networks， 2017， 70（2）： 132-140.

［15］" BANI I， ERVE R， EROVNIK

J. Edge， Vertex and Mixed Fault Diameters ［J］. Advances in Applied Mathematics， 2009， 43（3）： 231-238.

［16］" ESFAHANIAN A H， HAKIMI S L. Fault-Tolerant Routing

in DeBruijn Comrnunication Networks ［J］. IEEE Transactions on Computers， 1985， 34（9）： 777-788.

［17］" LATIFI S. On the Fault-Diameter of the Star Graph ［J］. Information Processing Letters， 1993， 46（3）： 143-150.

［18］" DU D Z， HSU D F， LYUU Y D. On the Diameter Vulnerability of Kautz Digraphs ［J］. Discrete Mathematics， 1996， 151（1/2/3）： 81-85.

［19］" CHEN X B. Edge-Fault-Tolerant Diameter and Bipanconnectivity of Hypercubes

［J］. Information Processing Letters， 2010， 110（24）： 1088-1092.

［20］" MA M J， WEST D B， XU J M. The Vulnerability of the

Diameter of the Enhanced Hypercubes ［J］. Theoretical Computer Science， 2017， 694： 60-65.

［21］" QI H， ZHU X D. The Fault-Diameter and Wide-Diameter of Twisted Hypercubes ［J］. Discrete Applied Mathematics， 2018， 235： 154-160.

［22］" XU M， XU J M， HOU X M. Fault Diameter of Cartesian Product Graphs ［J］. Information Processing Letters， 2005， 93（5）： 245-248.

［23］" BANI I， EROVNIK J. The Fault-Diameter of

Cartesian Products ［J］. Advances in Applied Mathematics， 2008， 40（1）： 98-106.

［24］" 徐俊明. 組合網(wǎng)絡(luò)理論 ［M］. 北京： 科學(xué)出版社， 2007：

1-333. （XU J M. Combinatorial Theory in Networks ［M］. Beijing： Science Press， 2007： 1-333.）

（責(zé)任編輯： 趙立芹）