關于模和圖與整和圖的一些新結論.pdf

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

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

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

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