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

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

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

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