路與星圖的強(qiáng)乘積圖的容錯(cuò)直徑

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

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

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

點(diǎn)容錯(cuò)直徑的上界， 以及兩個(gè)非平凡連通圖的強(qiáng)乘積圖的邊容錯(cuò)直徑的上界.

關(guān)鍵詞： 路； 星圖； 強(qiáng)乘積圖； 點(diǎn)容錯(cuò)直徑； 邊容錯(cuò)直徑

中圖分類號： O157.5" 文獻(xiàn)標(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è)計(jì)的研究， E-mail： li2006369@126.com.

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

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

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

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

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

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

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

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

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

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

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

［20］給出了增強(qiáng)超立方體的點(diǎn)容錯(cuò)直徑， Qi等［21］給出了扭曲超立方體的點(diǎn)容錯(cuò)直徑.

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

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

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

積圖的點(diǎn)容錯(cuò)直徑的上界， 以及兩個(gè)非平凡連通圖的強(qiáng)乘積圖的邊容錯(cuò)直徑的上界.

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

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

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

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

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

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

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

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

定義1" 令G1=（V（G1），E（G1））和G2=（V（G2），E（G2））是任意兩個(gè)連通圖， 則將G1和G2的強(qiáng)乘積記為G1G2， 定義其頂點(diǎn)集為V（G

1）×V（G2）. 若任意兩個(gè)不同的頂點(diǎn)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ù)強(qiáng)乘積的定義及文獻(xiàn)［1］的結(jié)論知， 對任意兩個(gè)連通圖G1和G2， 其強(qiáng)乘積G=G1G2是可交換的、 可結(jié)合的：

G1G1G2G1，

G1（G2G3）（G1G2）G3.

強(qiáng)乘積G的頂點(diǎn)數(shù)為

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

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

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

強(qiáng)乘積G的最小度為

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

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

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

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

和yv中至少有一個(gè)中心點(diǎn)或yu=yv且b-a=1或b-a=1且yu和yv中至少有一個(gè)中心點(diǎn). 圖1為3階路與4階星圖的強(qiáng)乘積圖P3

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

圖1" 強(qiáng)乘積圖P3S1，3

Fig.1" Strong product graph P3S1，3

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

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

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

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

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

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

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

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

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

2" 主要結(jié)果

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

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

推論1" 設(shè)G=PmS1，n-1是Pm和S1，n-1的強(qiáng)乘積圖， 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. 此時(shí)有mlt;n和mlt;3， 故有κ（G）=2.

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

引理2［2］" 設(shè)G1和G2是兩個(gè)任意連通圖， xayu和xbyv是G1和G2的強(qiáng)乘積圖G=G1G2中任意兩個(gè)不同頂點(diǎn)， 且有xa，xb∈V（G1）和yu，yv∈V（G2）， 則在圖G中頂點(diǎn)xayu和頂點(diǎn)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的強(qiáng)乘積圖， Pm和S1，n-1分別是m（≥2）階路和n（≥3）階星圖， 則G的直徑為

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

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

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

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時(shí)， d（G;xayu，xbyv）=m-1， 式（5）的不等式可取等號. 又因?yàn)閐（G）是在圖G中任意兩個(gè)頂點(diǎn)之間的最大距離， 故可得此時(shí)圖G的直徑為d（G）=m-1. 證畢.

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

≤w≤3， 圖G的點(diǎn)容錯(cuò)直徑為

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

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

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

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

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

情形1） m=2.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

情形2） mgt;3.

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

① xa=xb.

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

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

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

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

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

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

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

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

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

1→x2yv→x1yv，（15）

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

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

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

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

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

② yu=yv.

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

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

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

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

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

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

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

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

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

③ xa≠xb且yu≠yv.

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

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

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

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

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

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

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

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

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

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

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

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

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

之間的距離為d（G;x1y2，xmy2）=d（G）. 若令故障點(diǎn)集F={x2y1，x2y2}， 則在G-F中頂點(diǎn)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時(shí)， 由情形2）易得此情形下D2（G）≤d（G）+1， 若令故障點(diǎn)集F={x2y1}， 則在G-F中

頂點(diǎn)x1y2和x3y3之間的距離為

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

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

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

在G-F中頂點(diǎn)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的強(qiáng)乘積圖邊連通度為

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

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

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

λ（G）=3.（22）

證明： 因?yàn)棣耍≒m）=λ（S1，n-1）=1， 故由引理3可得λ（G）=min{3n-2，3m-2，3}. 又因?yàn)?n-2≥7且3m-2≥4， 故得λ（G）=3. 證畢.

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

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

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

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

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

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

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

情形1） m=2.

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

① xa=xb.

若yu和yv都不是中心點(diǎn)， 則在圖G中頂點(diǎn)xayu和頂點(diǎn)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中有一個(gè)頂點(diǎn)是中心點(diǎn)， 不妨設(shè)yu=y1， 則在圖G中頂點(diǎn)xay1和頂點(diǎn)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都不是中心點(diǎn)， 則在圖G中頂點(diǎn)xayu和頂點(diǎn)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都是中心點(diǎn)， 則可在圖G中頂點(diǎn)xay1和頂點(diǎn)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都不是中心點(diǎn)， 則在圖G中頂點(diǎn)xayu和頂點(diǎn)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中有一個(gè)頂點(diǎn)是中心點(diǎn)， 不妨設(shè)yu=y1， 則在圖G中頂點(diǎn)xay1和頂點(diǎn)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中的兩個(gè)頂點(diǎn)x1y2和x2y3. 若令故障邊集F={（x1y2，x1y1），（x1y2，x2y1）}， 則

在G-F中頂點(diǎn)x1y2和x2y3之間的距離為

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

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

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

情形2） mgt;3.

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

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

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

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

情形3） m=3.

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

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

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

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

路， 故有D′3（G）≤d（G）+1. 又因?yàn)镈′3（G）≥D′2（G）≥d（G）+1， 所以可得D′3（G）=d（G）+1. 證畢.

引理4（Menger定理）［24］" 設(shè)G是連通無向圖， x和y是G中不同的兩個(gè)頂點(diǎn)， 令κ（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）

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

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

（G）， G1和G2的強(qiáng)乘積圖G=G1G2的點(diǎn)容錯(cuò)直徑滿足：

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為故障點(diǎn)集， 且有F=w-1. 不失一般性， 不妨設(shè)d（G-F）=h. 則當(dāng)h≤1時(shí)， G-F是完全圖， 從而在G-F中x和y

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

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

1n2， 故可得圖G發(fā)生點(diǎn)故障后， 頂點(diǎn)總數(shù)與x和y之間的內(nèi)點(diǎn)不交路的頂點(diǎn)數(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是兩個(gè)非平凡連通圖， 階數(shù)分別為n1和n2， 邊連通度分別為λ1和λ2， 最小度分別為δ1和δ2

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

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中任意兩個(gè)不同頂點(diǎn)， 且使得x和y之間的距離為d（G-F;x，y）=h.

由Menger定理可知， 在G-F中x和y之間至少存在（λ（G）-t+1）條邊不交路， 且每條路的邊數(shù)至少為h. 又因?yàn)閺?qiáng)乘積圖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)點(diǎn)或邊不交路的方法， 再結(jié)合星圖的中心性， 給出了路與星圖的強(qiáng)乘積圖的點(diǎn)容錯(cuò)直徑和邊容錯(cuò)直徑. 結(jié)果表明， 路與星圖的強(qiáng)乘積圖擁有較小

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

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

參考文獻(xiàn)

［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é)任編輯： 趙立芹）