圖的L（p，q）-標號問題研究.pdf

1、學校代碼10345研究類型一廛旦垂熊塹窺浙江師范大學碩士學位論文題目：圖的墜垃，91：盤量圈塑盟塞S￡望亟Y(jié)Q里照Q￡!Qb!￡盟Q￡L(旦：q)：墜自魚￡li望gQ!=魚￡目星照5學科專業(yè)乙廛旦塾堂，一一～——年級：2003級學號：200320122研究生：叁盤疊指導教師：疊整堡型塾蕉一中圖分類號：垡堇!上答辯時間：2006年上月sTuDYoNTHEPRoBLEM0FL(p，q)LABELINGoFGRAPHsABSTRCTTheL(

2、p，q)一labeliⅡgofgraph8盯i8esfromav私iationfrequencya8signmentproblembyHaleGivena竄aphGandtwopositiveinteger8p≥q，anm—L(p，g)一l￡山elingofGi8afunction，：y(G)一o，1，2，，m)suchthat，foranytw0Vertice8。，掣∈y(G)，I，(茹)一，(剪)l≥pifdG(。，掣)=1；and

3、I，(罩)一，(掣)l≥gif奶(z，暑，)=2TheL0，g)一nunlberofG，denotedbyAM(G)，isthe8malk8tnumbermsuchthatGhasanm—L(ng)一IabelingInt11isthe8i8，we丑rstly8ummarizethemainresultsandevolutionontheL(p，q)labelinginrecent”ar8，thenWe、】lrillinve8tigat

4、etheL(1，1)一1abelingandtheL(2，1)一1abelingoftheliIlegraphL(G)ofa8implegraphGⅥ札hma婦m啪degree△(G)≤4weu8uauydenotedby強口(G)theL(p，q)一labeungnuHlberofL(G)FinauyweexploretheL(p，q)一18belingproblemof80mecl明8e8ofgraph8TheL(1，1)一labe

5、ungofL(G)i8aⅡaiogol】8tothe骶rongedgecolo血gofgr印hGwbdenotedthe8trongedgechromaticindex(theli8tstrongedgechromaticindex)ofGby嵌7(G)(s磁(G))，thensx，(G)=Ai1(G)1In1985，Erd68andⅣ甜etf釘c0Ⅱje毗uredth砒for舭l(fā)y8implegr8phG，Sx7(G)≤5△2(G)／

6、4wheⅡ△(G)i8e嘲舡ldsx，(G)≤5△2(G)／4一△(G)／2l／4when△(G)isoddBDr△(G)=4，theconjecturedboundi820，previouslnHor毛kprovedS一(G)≤23F0r△(G)=3，theconjecttlredboundis10，tlli8boundh8sbeenprovedbyAnderson，arldindependentIy，Hor矗keta1Inthj8t

7、hesis，weshowth8ts弼(G)≤22when△(G)=4Furthermore，ifthegirthg(G)≤4，thensx’(G)≤21sincesx7(G)≤sx：(G)，80’veimpro、redthere8ultofHor酞A180，wepravedthatif△(G)=3，thensx：(G)≤11ForgraphGwith△(G)≤4，GeorgesandMaur0proved心l(G)s2(△(G)一1)(

8、△(G)2)wjimpravedthisboundtothatA；1(G)≤2△2(G)一2FinallyWe唧10retheL(pq)一IabelingofkdegeneratedandMm曲出ed8umG1M島ofG1鋤dG21npartielllar，Wepres齜ctheatt咖ableldw聊andtheupperbound8forcactu丑andunicydeKEYwoRJDs：L(p，q)一labeling，edge_L