摩天輪圖的優美性

在輪圖Wn圈上的每一個頂點都粘接一個長為m的路組成的圖為摩天輪圖，記為Mn（m）。本文研究摩天輪圖Mn（m）及證明了M3（m）的優美性。

1引言及定義

優美圖是圖論中極有趣的研究課題之一，上世紀六十年代中期，圖標號問題被提出，而圖標號問題中優美標號是最先提出的一類，由于它的趣味性和應用性很快受到國內外學者的重視。至今，已有大量的相關論文被發表，本文證明了摩天輪圖M3（m）的優美圖。

對于一個簡單圖G（V，E），如果對每一個v∈V，存在一個非負整數θ（v）（稱為頂點v的標號）使滿足：

（1）?u，v∈V，如果u≠v，則θ（u）≠θ（v）；

（2）max﹛θ（v）│v∈V﹜=│E│

（3）?e1，e2∈E，如果e1≠e2，則θ′（e1）≠θ′（e2）其中

θ′（e）=│θ（u）—θ（v）│，e=uv則稱G為優美圖.稱θ為G的一個優美標號。

定義2在輪圖Wn圈上的每個頂點都粘接一條長為m的路組成的圖為摩天輪圖，記為M n（m）。

2主要研究結果

摩天輪的優美性

當n=3時，M3（m）是優美圖。

證明：如圖1，摩天輪圖M3（m）共有3m+4個頂點，3m+6條邊，其頂點依次記為x0， x1， x2， x3m+3.

定義Mn（m）的頂點標號θ為

θ（x0）=0

θ（x1）=1

θ（x2）=3m+5

θ（xm+2）=3

θ（xm+3）=3m+4

θ（x2m+3）=3m+6

θ（x2m+4）=4

θ（x2i+1）=3i+2 （i=1，2，）

θ（x2i+2）=3m-3i+5 （i=1，2，）

θ（xm+2i+2）=3+3i （i=1，2，）

θ（xm+2i+3）=3m-3i+4 （i=1，2，）

θ（x2m+2i+3）=3m-3i+6 （i=1，2，）

θ（x2m+2i+4）=4+3i （i=1，2，）

其最大標號為θ（x2m+3）=3m+6=│E│。

由上定義易知， θ為V（Mn（m））到{0，1，2， …， │E│}的一個單射。

則由定點標號可推出邊標號θ′為：

θ′（x0 x1）=1

θ′（x1 xm+2）=2

θ′（x0 xm+2）=3

θ′（x0 x2m+3）=3m+6

θ′（x1 x2m+3）=3m+5

θ′（xm+2 x2m+3）=3m+3

θ′（x1 x2）=3m+4

θ′（xm+2 xm+3）=3m+1

θ′（x2m+3 x2m+4）=3m+2

θ′（xi xi+1）=

下面給出M3（5）的優美標號。