關(guān)于圖的L（3，2，1）標(biāo)號的若干結(jié)果.pdf

1、山東大學(xué)碩士學(xué)位論文關(guān)于圖的L（3，2，1）標(biāo)號的若干結(jié)果姓名：劉延軍申請學(xué)位級別：碩士專業(yè)：運籌學(xué)與控制論指導(dǎo)教師：劉家壯2002.12.8山東大學(xué)碩士學(xué)位論文l 廠G ) 一s ( y 】≥2 ；老i d ( x ，y ) = 3 ，貝, J l s ( x ) - s ( y 】≥1 。圖的一個七- L ( 3 ，2 ，1 )標(biāo)號是圖的一個三( 3 ，2 ，1 ) 標(biāo)號，使得所有的標(biāo)號都小于等于七，并至少有一，一’個達(dá)到k 。圖G

2、 的L ( 3 ，2 ，1 ) 標(biāo)號數(shù)用丑，( G ) 表示。! 本文研究了對最大度為△的一般圖的標(biāo)號數(shù)的上界，但主要針對某些特殊圖的特殊結(jié)構(gòu)對它們的L 0 ，2 ，1 ) 標(biāo)號進行了研究，并得到了部分結(jié)果。f ，本文共分五部分：第一部分簡單介紹了圖論的基本概念以及圖的標(biāo)號理論的歷史。簡單介紹了前人等關(guān)于圖的標(biāo)號的一些重要結(jié)果。第二部分針對有最大度為△的任意圖的￡( 3 ，2 ．1 ) 標(biāo)號進行了研究，得出了定理2 ．1 ．1 ：對有最

3、大度為△的任意圖G ，有丑，( G ) ≤A 3 + 岔+ 3 A 。并對一般圖的上( 3 ．2 ，1 ) 標(biāo)號數(shù)的上界作了改進得出了定理2 ．2 ．1 ：對最大度為△的任意圖G ，有“G ) < ( 是) ·( ( △一，) ' _ ’- - 1 1 ¨( ¨) 2第三部分給出了平面三角剖分圖與立體四面體剖分圖的定義，并得出了它們的上界。定理3 ．1 ．1 ： 對最大度為△的一般平面三角剖分