一类线图的带宽

一类线图的带宽 JORrDaJofMat[mmaticalRc~c&rcll&Exposition Vo1.19No3.495500.Au~as$1999 TheBandwidthofaClassofLineGraphs 0,TaoWANGJan {hastofMat,hSci..DalianUniversityofTcchaoh~gy116024) Abstract:Thehandwhlthofa(lsoflinegraphsand given. Keywords:graph;baudwidth. Classification:AMSf1991)05C/CLC()1575 Documentcode:AArticleID:I{H10—341X(1999)03—0495—66 1.Introduction Inbivariatesplinetheory,inordertosolveeffectivelythelinearequationscorrespond? hagtotheglobalconformalityconditionwecangiveasuitablenumberingofthegrid— segmentsofthepartitionsothatthecoefficientmatrixofthelinearequationsisaband matrix.Wecallitthenumberingproblemofthepartitions.Eachpartitioninthenlllll- beringproblemhasacounterpartgraphForexample,thefamouspartitionproposedby MorganandScott(seeFigure1)isequivalenttothenumberingofedgesofthegraph showninFig’ure2.Inpractice,oneitlayencounterapartitionwhosecounterpartisshown inFigure3. Inthispaper,thenumberingproblemoftheedgesofsuchgraphsisdiscussed.Let G=(E)beagivengraphand:E{1,2,.,E1)beanumberingofitsedges.For any?V.define: D() D(G) D(G) max(1(?”1 max{D(“) min{D(G) ~2(vw1:itL,EEvw?E) ?) isanumberingofE} (1) (2) (3) D(口)iscalledthebelt—lengthofthenumberingforvertexandD(G)thebelt-length ofthenulnberingforagraphG.D(C)iscalledthebelt—lengthofG Itiseasytoseethatthebelt-lengthofanynumberingforgraphGisequaltothe bandwidthofthemmiberingforthelinegraphL(C)Sothebelt—lengthofGise qual Receiveddate:l095-(J605 Biography:QiTao{1962-】 Itltt]eborltin.Tiangsuproviltce.Ph.D,currently7tlla~sociaLeprofessor “tBeijingUniversityofPo~tsaatdTc[ecoztllltllhiCa.tions. 495 tothebandwidthof ,(G)Thebandwidthproblemhasbeenextensivelystudied,but thereareordyafewgraphswhosebandwidthsareknown【cf_[3]fordetaiL).Inthis paper,wediscussaclassofspecialgraphswhichcomesfromsplinetheory.Wewillde— terminetheirbelt—lengthandgiveoptimalnmnberingoftheedgesofgraphsmtheclass. Figurel Foranypositiveintegers1and s?3,theMorgan—ScottGraph,a(k,is defittedasfollows: (i)c(k,)isasimplegraphwithks vertices; cn)Thesetoftheinteriorverticesof c(k,)formsacycleoflengths,andthe degreeofeveryelementofthesetis+1. Herethesetofinteriorverticesofa graphconsistsofallitsverticessuchthat thedegreeofisgreaterthanone. 1 2 Figure2 1 2 l 2 ItiseasytoseefromthedefinitionthatG(1s)lSaconnectedgraphswithedges. Underthisdefinition,thegraphsinFigure2andFigure3areknownasc(z,3)an da(k,5) respectively.Themainresultofthispaperisfollowing: TheoremLeta(k,s)beaMorgan—Scottgraph.Then D(a(k,s))={2k一【币k+1]r2. 12k一 496—— 2n+1and= 2n+land? 2n. (4) . \,,,. hthenextsection,weshowthattherighthandsideof{4)isalowerboundof D(a(k3)),and,inSection3,wpresentanumberingofc(k,3)whichachieVesthe l0er hound,establishingthetheorem. 2.Alowerboundofthebelt—lengthforG(k.s) Wefirst百veaupperboundofD(C(k,s))bypresentingaconcretenumberingofthe edges: Proplosition1Let?1and?3beanytwointegers.Thenv(c(ks))?2k Pro0fLetint(G(k,))={? (I,..,as-1)whichformsthecyde{‰…,(is--1).LetEbe thesetofauedgesofc(k,),andEl:{n?E:a(u):1).ThenEhasapartitionas where?=no.LetA={1,.,七一1)andn+Abetheset{?+1 thenumberingisgivenby = 二簿 一 : Proposition2Letc(k,)beaMorgml-Scottgraph,Then (5) n+一l.Then (6) (7) (8) ProofWestilladoptthenotations_mProposition1andsetr(n):{u口:u”?E) foranyvertexofc(ks).1etbeanynumberingofE,thatis,isabijectionfromE into{1,2,…,).Withoutlossofgenerality,wemaysupposethat一(1)?F(a0).For everytwith0<t【(一0/21,let=(aod1,…毗,as-l,…,n一},and, FUr(u) 1?m (9) Thenh=Irmlx((r))?IrtIholdsSince一()?F,,thereexistsanumSerm0”l? , , 497 } 1 — 5 1 0 = } ? 毗 rt U E .=U? 一 E n =? 南 dd nn aa 11 ++ 佗n几 222 ==一 55 一一 七 222 ,????,,??I, >一 S 南 G D suchthat一(h)?r(d)If0?”t,then 0ntheotherhand D(.u1 D(n1) 2Iv(a--a)一lI1 2l~(ala2)一(口【IdI) D(0,一1)2f(m一1口,),(口m-1口2) D(d)三lh一(0—1a)l D(G(S))2max(D(),.D(?))2 Since0mStandhFtl2k一 ,一 【 (12) f131 (141 holdsfors=2n十1Bythearbitrarinessof,D(G(k,5))hastheSalVelowerboundas iIL(12)and(13). Furthermore,whens=2n+1andk=n,(131Callbeimprovedto D(C(k,s))2k SupposetothecontrarythatthereexistsanumberingsuchthatD?(G(,))=2k一1. Thishnpliesthata?inequalitiesin(10)and(I1)becomeequalitieswhenissubstituted for.Suppose一(1)?r(a【】)and一(ks)?r(a,)Itiseasytoseethat”l=nor m=+1.BythesynunetricpropertyWemay~ssuIIlethatm=n.Thus D(d(】)=2k—l(0?口1)一1, D(ai)=2k一1=(?t+1a1)一(ai~i D…a)=2k1=sk,(,1d,). 498一 (151 Let r11 ?=U工1(),A2=U工1(啦) =1…+1 ThenE=A1UA2UE)UEBy(14),wehave 2k(A1)sk2k+1.(16) ConsiderthesetA={l,..,).n(E)isanemptyset,forotherwiseD.(?)sk— k=2nk>2k1.Thistogetherwith(15)impliesAC(?2UE.).SinceIEt)I=k1,we havem=mi~(99(?2))k.ConsidersetL={2n+1,...,sk}.Bythesalrleargument, M=inax((?2))2nk+1Suppose盯?(r(a4)andM?(r()】,where n+1i,Js一1.Consideringthebelt—lengthforai,..,d,wehave .’(G(,))…(.…,.t(町))南M+l一2nk—k+1 : 2k1+一1 >2k一1. ThiscontradictstheassmnptionthatD?(a(k,s))=2k一 1.Sotheproofiscomplete. 3-Anoptimalnumbering Whenk<nork=nands=2n+1,(6)and(7)havegivenanoptimalnumbering ofG(,5).Inthissection,wegiveanoptimalnumberingfortheremainingcases Set … {n+l—s=2…nand…k>n,…) ItiseaYtoseethatirkholdsforeachpositiveinteger5when0iThisimp~es 1+(2k—r)?A2;1(for1in)(18) whereAi=ik+Afori=0, 1,..51,and,A={1,2,..,).Whens=2nandk三n, itiSeasytosee ir?k一1(for0i<s—n).(19) Witens=2n+1andkL)n.wehave k >_l>r. nn+1 Thisalsoimpliesthat(19)isvalidUsing(18),weget: k+(2kr)i?A21(for0i<51 Nowwemaydefinethenumberingasfollows: {二鼎叫, 499 (201 (21) and , 一= A2i-I , ItiseasytoseethatD()=2—rexceptthat D(‰)+(n一1)r, +r,l, 1<i<他 n<i<s. s=2n. s:2n+1 (22) Inbothc~.sesD(n)2k—r.SoD(G)=2k—r. Nowwehavepresentedanumberingwhosebelt—lengthisequaltothelowerb ound Thismeans(4)holds. RefeFences 1】ChvAt’alovAJ.OpthnattabetS.gofaproductoftwopaths[J】.DiscreteMathealatics.1975 11:249253. 21HarperLH,OpthnMnunJbcringsomdi,~operimetricprobtemso儿graphs【J】.JonrnalofCo,I卜 binationialTheory.19661:385393. 3】Chim,PZ,etc.ThebandwidChprobJemforgraphsaudnla~rJ’ces—Asurvey口】.Journalof GraphTheory,1982.6:223254. 4】HararyF.Pro])h:m16InTheoryofgraphs?itsapplications【c】MFiedlerEd.,Czechoslo- yakAcademyofScience.Pragl,e(1967). 5】l1_HongWal~g.TIJedimensionjdb;~isofspacesofH~,ttivaratespllnes 【.1]J.Journ;dof Computationa/7tll(1AppliedMathen~tics.198512&13:163177. 一c 馒,完任寸享 一 类线图的带宽 漆涛,王军 大连理工大学数学科学研究所,116024) 摘要:本文给出了一类绒陶的带宽,并给出了它的最佳编号 一 500一 ,I??【【