關(guān)于模和圖與整和圖的一些新結(jié)論.pdf

1、圖論是數(shù)學(xué)的一個(gè)分支，特別是離散數(shù)學(xué)的一個(gè)重要分支，它在物理、化學(xué)、天文、地理、生物學(xué)，尤其是計(jì)算機(jī)科學(xué)中有非常廣泛的應(yīng)用. 圖的標(biāo)號(hào)問(wèn)題的研究源自于1967年Rosa的一篇論文《Oncertainvaluationoftheverticesofagraph》.圖G的頂點(diǎn)標(biāo)號(hào)是標(biāo)號(hào)f到G的頂點(diǎn)分配，使得對(duì)每一條邊uv，推出的標(biāo)號(hào)依賴于頂點(diǎn)標(biāo)號(hào)f(u)和f(v).早在1988年，Harary介紹了和圖的概念，圖G(V,E)被稱為和

2、圖(Sumgraph)，若有個(gè)從頂點(diǎn)集V到正整數(shù)集合S的單射f，uv∈E當(dāng)且僅當(dāng)f(u)+f(v)∈S.在和圖中，由于具有最大標(biāo)號(hào)的那個(gè)頂點(diǎn)沒(méi)有與之相鄰的頂點(diǎn)，所以每一個(gè)和圖都一定包含孤立點(diǎn)，對(duì)于一個(gè)連通圖G，我們令σ(G)表示使得圖G成為和圖的最少孤立點(diǎn)的個(gè)數(shù)，稱為G的和數(shù). 在1990年，J.Boland，R.Laskar，C.Turner和J.Domke提出了模和圖的概念，圖G(V,E)被稱為模和圖(Modsumgraph

3、)，若存在一個(gè)正整數(shù)n和一個(gè)從頂點(diǎn)集V到{1,2，…，n-1}的單射f使得對(duì)某個(gè)頂點(diǎn)w，有：uv∈E當(dāng)且僅當(dāng)f(u)+f(v)=(modn)=f(w).顯然所有的和圖都是模和圖，反之不成立.對(duì)于一個(gè)連通圖G(V,E)，如果它不是模和圖，則我們用ρ(G)來(lái)表示使得G成為模和圖的最少孤立點(diǎn)的個(gè)數(shù)，稱其為G的模和數(shù). 在1994年，Harary又進(jìn)一步推廣了和圖的概念，允許S是全體整數(shù)集，即對(duì)于圖G(V,E)，如果存在有頂點(diǎn)集V到全體

4、整數(shù)集Z的一個(gè)映射標(biāo)號(hào)λ滿足：uv∈E當(dāng)且僅當(dāng)λ(u)+λ(v)=λ(w)，其中u，v，w∈V，則稱圖G為整和圖(Integralsumgraph).并非所有的連通圖都是整和圖；對(duì)于一個(gè)連通圖G，如果它不是整和圖，則我們用ξ(G)來(lái)表示使得G稱為整合圖的最少孤立點(diǎn)的個(gè)數(shù)，稱其為G的整和數(shù). 本文取得的主要工作可概括如下：1.在本文第三章第二節(jié)中，證明了一類新型的模和圖，，. 2.在本文