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

1、山東大學(xué)碩士學(xué)位論文關(guān)于圖的L（3，2，1）標(biāo)號(hào)的若干結(jié)果姓名：劉延軍申請(qǐng)學(xué)位級(jí)別：碩士專業(yè)：運(yùn)籌學(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 。圖的一個(gè)七- L ( 3 ，2 ，1 )標(biāo)號(hào)是圖的一個(gè)三( 3 ，2 ，1 ) 標(biāo)號(hào)，使得所有的標(biāo)號(hào)都小于等于七，并至少有一，一’個(gè)達(dá)到k 。圖G

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

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