Flower Snark圖與Knodel圖的親切素標(biāo)號(hào).pdf

1、圖的標(biāo)號(hào)問(wèn)題是圖論中一個(gè)比較新的課題，它可追溯到1950年信號(hào)帶寬的優(yōu)化問(wèn)題：源于主要的非零數(shù)字信號(hào)通常位于一個(gè)比較窄的帶寬中。1966年Rosa給出了圖標(biāo)號(hào)的一個(gè)新的概念--圖的優(yōu)美標(biāo)號(hào)(Graceful Labeling)，并提出了著名的所有的樹(shù)都是優(yōu)美的猜想。圖的標(biāo)號(hào)是指在一定規(guī)則條件下對(duì)圖的頂點(diǎn)與邊進(jìn)行標(biāo)號(hào)。一個(gè)圖的頂點(diǎn)標(biāo)號(hào)是圖的頂點(diǎn)集到整數(shù)集的映射，而邊標(biāo)號(hào)則是圖的邊集到整數(shù)集的映射，根據(jù)對(duì)映射的不同要求，產(chǎn)生了各種類型的圖的

2、標(biāo)號(hào)，例如優(yōu)美標(biāo)號(hào)、超幻和標(biāo)號(hào)、調(diào)和標(biāo)號(hào)和親切素標(biāo)號(hào)等等。 圖的親切素標(biāo)號(hào)是由Sumndarm，Ponraj和Somasundram于2005年提出來(lái)的。如果一個(gè)帶有頂點(diǎn)集V的圖存在一個(gè)從V到{l，2，……|V}雙射f,對(duì)每條最大公約數(shù)gcd(f(u)，f(v))=1的邊標(biāo)號(hào)為1，并且對(duì)最大公約數(shù)gcd(f(u),f(v))>1的邊標(biāo)號(hào)為0，則標(biāo)號(hào)為l的邊的數(shù)量和標(biāo)號(hào)為0的邊的數(shù)量相差最多為l，這類圖被稱作有親切素標(biāo)號(hào)。

3、 G是一個(gè)簡(jiǎn)單的非平凡的連通的三正則圖，點(diǎn)集V(Gn)={ab,bb,cb,di:0≤i≤n-1}，邊集E(Gn)={aiai+1,bibi+1,diai,dibi,dici:0≤i≤n-1}，點(diǎn)的標(biāo)號(hào)對(duì)n取模，Hn可以由Gn通過(guò)用邊bn-lc0,cn-1b0替換6n-1b0,cn-1c0得到。如果n為奇數(shù)且n≥5,Hn被稱作Flower Snark圖。其他的圖，被稱作Flower Snark圖的相關(guān)圖。 Sumndarm等證明