摘　要

圖的標號問題起始于1966年A.Rosa的著名的優(yōu)美樹猜想。一個圖的頂點標號是圖的頂點集到整數(shù)集的映射，而邊標號則是圖的邊集到整數(shù)集的映射。根據(jù)對映射的不同要求，產(chǎn)生了各種類型的圖的標號問題。本文對圖Skolem優(yōu)美標號和調(diào)和標號兩類問題進行研究，分別解決了這兩類標號中的一些問題和猜想，取得了較好的結(jié)果。
優(yōu)美標號在射電天文學及計算機網(wǎng)絡(luò)理論中有著廣泛的應(yīng)用。Skolem優(yōu)美標號是優(yōu)美標號的一個衍變。k-星圖是由五個任意大小的星圖組成的非連通圖。對k-星圖優(yōu)美性，Kishore猜想當且僅當有一個星是偶星 時，k-星圖是Skolem優(yōu)美的。Choudum和Kishore等人證明了這個猜想 時成立。本文對任意的k-星圖的Skolem優(yōu)美性進行研究，針對k-星圖和Skolem優(yōu)美標號的特點，設(shè)計了相應(yīng)的分支限界搜索策略。
調(diào)和標號是為解決糾錯碼的問題而由優(yōu)美標號衍變而來的。徐士達證明了當且僅當 時，三角蛇圖是調(diào)和圖。本文證明了所有的雙三角蛇圖都是調(diào)和圖。Deb和Limye提出猜想：所有的多貝殼圖都是調(diào)和圖，并證明了對平衡2貝殼圖和平衡3貝殼圖Deb猜想成立。楊元生等人證明了對平衡4貝殼圖Deb猜想成立。本文證明了對平衡5貝殼圖Deb猜想也成立。

關(guān)鍵詞 Skolem優(yōu)美標號 調(diào)和標號
Abstract

Graph labeling traces its origin to the famous conjecture that all trees are graceful presented by A.Rosa in 1996. Vertex labelling is a mapping from the vertex set to integer set. On the other hand, edge labeling maps edge set into integer set. According to the different requirements for the mapping, many variations of graph labelings have been evolved. In this paper, combining the computer constructure prove with mathematical prove, two classes of graph labelings: skolem graceful labeling and harmonious labeling are researched, some problems and conjectures have been solved redpectively.
Graceful labelings serves as useful models for a broad range of applications such as astronomy and communication networks. The Skolem graceful labelings have been invented analogues of graceful graphs by modifying the permissible vertex labels. The k-stars graph is a disjoint union of k stars with random size.
Hamonious labelings arise in the study of additive bases problems stemming from errorcorrecting codes. Xu Proved the triangular snake graph is harmonious if and only if .We prove all double triangular snake graphs are hamonious. Deb and Limy’s conjecture that all multiple shells are harmonious and have shown that the conjecture is true for the balanced double shells and balanced triple shells,Xu,Xi, and Qiao Proved the conjecture is true for balanced quadruple shells.

Key Words skolem graceful labeling harmonious labeling

目 錄

摘　　要 Ⅰ
Abstract Ⅱ

第1章 緒 論 1
1.1 圖論的基本概念及相關(guān)知識 1
1.2 標號問題的研究現(xiàn)狀 3
1.2.1 優(yōu)美標號 3
1.2.2 調(diào)和標號 4
1.3 本文工作 6
第2章 圖的優(yōu)美標號 8
2.1優(yōu)美標號的相關(guān)概念及發(fā)展概況 8
2.1.1 優(yōu)美圖的相關(guān)概念 8
2.1.2 優(yōu)美圖的發(fā)展概況 9
2.2 圖的Skolem優(yōu)美標號 12
2.2.1 k-星圖的Skolem優(yōu)美標號 12
2.3 小 結(jié) 19
第3章 圖的調(diào)和標號 20
3.1 調(diào)和標號的相關(guān)概念及發(fā)展概況 20
3.1.1 調(diào)和圖的相關(guān)概念 20
3.1.2 調(diào)和圖的發(fā)展概況 21
3.2 雙三角蛇圖的調(diào)和標號 22
3.3 平衡5貝殼圖的調(diào)和標號 26
3.4 小 結(jié) 32

結(jié)　論 33
致　謝 34
參 考 文 獻 35
附錄1 37
附錄2 42