复杂网络课后习题答案exercises-on-chapter4

ExercisesonChapter44.1RoutingsinInterconnectionNetworks4.1.1Provethatτ(G)≤τ(T)foranyconnectedspanningsubgraphTofaconnectedG.4.1.2Countthevertex-forwardingindexandtheedge-forwardingindexofPetersengraph.4.1.3Countthevertex-forwardingandedge-forwardingindicesofapathPnandastarK1,n−1forn≥3.4.1.4ProvethatifGisa2-connectedgraphofordernthenτ(G)≤12(n−2)(n−3)andthisboundisbestpossibleinviewofK2,n−2.4.1.5Thesymbolsτδ,nandπδ,ndenotetheminimumofτ(G)andπ(G),respectively,takenoverallgraphsGofordernwithminimumdegreeδ.Provethatτδ,n=l2(n−1−δ)δmandπδ,n=l2(n−1)δmforanynandδwithnδ≥1.4.1.5Provethatforeachi=1,2,ifGi=(Vi,Ei)isaconnectedgraphwith|Vi|=niand|Ei|=εi,thenτ(G1×G2)≥n2n1Xu1∈V1Xv1∈V1\{u1}(dG1(u1,v1)−1)+n1n2Xu2∈V2Xv2∈V2\{u2}(dG2(u2,v2))−1)+(n1−1)(n2−1)π(G1×G2)≥minn2ε1X(u1,v1)∈V1×V1dG1(u1,v1),n1ε2X(u2,v2)∈V2×V2dG2(u2,v2).4.1.6Provethatτ(G)≤(n−1)d(n−k−1)keifGisak-connectedundirectedgraphofordern,wherek≥1.4.2Fault-TolerantDiameter4.2.1LetF(t,d)denotetheminimumdiameterofanalteredgraphobtainedbyaddingtextraedgestoagraphwithdiameterd.Provethat(a)F(t,d)≤F(t,d0)andg(t,d)≤g(t,d0)ford≤d0;(b)F(t,g(t,d))≤d≤g(t,F(t,d)).4.2.2LetP(t,d)denotetheminimumdiameterofanalteredgraphGobtainedfromasinglepathofdiameterdplustextraedges.Provethat(a)P(t,(2k−1)t+h+1)≤2kforanyintegerst,kandhwith0≤h≤2k−1;1(b)P(4,5(2k−1)+h)≤2k+1foranyintegerskandhwith2≤h≤5;(c)P(5,6(2k−1)+h)≤2k+1foranyintegerskandhwith2≤h≤6.4.2.3ProvethatF(t,d)=P(d,t)foranypositiveintegerstandd.4.2.4Provethatforgivenpositiveintegerstandd,dt+1≤P(t,d)≤d−2t+1+3.Inparticular,P(t,(2k−1)(t+1)+1)=2kforanypositiveintegerkandF(t,d)≤jdtk+1ifkisenoughlarge.4.2.5Provethatforanyintegerd(≥4),d5≤P(4,d)≤d5+1andd6≤P(5,d)≤d6+1.4.3Menger-TypeProblemsinParallelSystems4.3.1Provethatrw(Qn)=Dw(Qn)=(n,for1≤w≤n−1;n+1,forw=n.4.3.2Provethatrw(B(d,n))=Dw(B(d,n))=n+1,for1≤w≤d−1.4.4WideDiameterofNetworks4.4.1LetxandybetwoverticesinQnwithdistancel(0).Then,foranyintegertwith0≤t≤n−2,dn−t(Qn;x,y)=(l,ifn−t≤l;l+2,ifn−tl.4.5(l,w)-Independenceand-DominatingNumbers4.5.1Provethat(a)α2,n(Qn)=(2,ifn=2;2n,ifn≥3;(b)α3,n(Qn)=2n−1ifn≥3;(c)αn,n(Qn)=(4,ifn=3;2,ifn3;(d)αn−1,n(Qn)=8,ifn=3,4;4,ifn=5,6;2,ifn≥7;(e)αd,n−t(Qn)=αd,n(Qn),where0≤t≤n−2and1≤d≤n−t−1.24.6RestrictedFault-ToleranceofNetworks4.6.1Provethatif(x,y)isasymmetricedgeinKautzdigraphK(d,n)(d≥2,n≥2),thenthesetE+({x,y})ofout-edgesfrom{x,y}isarestrictededge-cutinK(d,n).4.6.2Provebyusingtheexercises2.3.1,2.3.2andtheexercise4.6.1that(FanandXu[1])(a)λ0(K(d,n))=(notexistn=1,d=2;2d−2,d≥3,n=1ord≥2,n≥2.(b)4d−5≤λ0(UK(d,n))≤4d−4,d≥3,n≥34.6.3LetGbeanon-optimalandvertex-transitivegraphofdegreek.Thenλ0(G)=kifandonlyiftheinducedsubgraphG[X]isacompletegraphoforderkforanyλ0-atomXofG.4.6.4LetGbeanon-optimal,k-regularandconnectedgraph.IfGcontainsacompletegraphKk,thenX=V(Kk)isaλ0-atomofG,and,henceλ0(G)=k.4.6.5LetGbeanon-optimalandconnectedvertex-transitivegraphwithdegreek(≥3).Thenλ0(G)=kifandonlyifGcontainsacompletegraphoforderk.4.6.6LetGbeanon-optimalandconnectedvertex-transitivegraph.ThenGhasaprefectmatching,andhenceGhasevenorder.4.6.7CompletetheproofofTheorem4.6.10(b).References[1]FanYing-MeiandXuJun-Ming,Restrictededge-connectivityofKautzgraphs(inChi-nese),toappearinAppliedMath(2004)No.3.3