摘　要

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

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

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