關于Mobius梯的細分圖的親切性

摘要:一個簡單圖G(V，E)被稱為是親切的(Coridal)，若存在映射f:V(G)→{0，1}，使得導出映射f*(u，v)→|f(u)-f(v)|，滿足:|vf(0)-vf(1)|≤1且|Ef(0)-Ef(1)|≤1。

設G是簡單圖，在G的每相鄰兩頂點之間加入一個頂點后所得到的圖稱為G的細分圖，文章證明了Mobius梯的細分圖是親切的。

關鍵詞:Mobius梯 細分圖 親切圖

1 概況

定義:對于一個簡單圖G(V，E)，若存在映射f:V(G)→{0，1}，導出映射f*:E(G)→{0，1}，使得導出映射f*(u，v)→|f(u)-f(v)|，滿足:|vf(0)-vf(1)|≤1且|Ef(0)-Ef(1)|≤1。

定義:設G是簡單圖，在G的每相鄰兩頂點之間加入一個頂點后所得到的圖稱為G的細分圖，記為S(G)。

當G是親切圖時，G的細分圖S(G)不一定是親切的，比如:回路C3是親切的，但其細分圖C6是不親切的，但C6的細分圖C12有是親切的，C4是親切的而且其細分圖C8也是親切的，因此，當G是什么圖時，細分圖S(G)也是親切的，這是一個饒有興趣的問題。

本文討論Mobius梯細分圖的親切性，證明了Mobius梯的細分圖是親切的。

2 主要結果及證明

Mobius梯是將階梯PmxP2的兩對角再用邊相連所得到的圖(如圖所示)，記為Mm，我們有:

定理:對任意的正整數n≥2，Mobius梯的細分圖S(Mn)是親切圖

證明:設在圖S(Mn)中，用yj(i)表示在相鄰兩頂點xj(i)和xj+1(i)之間加入的頂點(i=1，2;j=1，2，，，n-1)，用zj(j=1，2，，，n)表示在相鄰兩頂點xj(1)和xj(2)之間加入的頂點;用ω1表示在相鄰兩頂點x1(1)和xn(2)之間加入的頂點，用ω2表示在相鄰兩頂點x1(2)和xn(1)之間加入的頂點，這樣得到Mobius梯Mn的細分圖S(Mn)

下面分兩種情況證明

2.1 當n為偶數時

S(Mn)的頂點標號f如下

f(ω1)=1f(ω2)=0

顯然所有標號為0的點的個數與標號為1的點的個數相等。

則有:

顯然所有標號為0的邊的個數與標號為1的邊的個數相等。

因此，當n為偶數時，S(Mn)是親切的。

2.2 當n為奇數時

S(Mn)的頂點標號f如下:

f(ω1)=1 f(ω2)=0

顯然所有標號為0的點的個數與標號為1的點的個數相差1，即|V(1)-V(0)|=1。

則有;

顯然所有標號為0的邊的個數與標號為1的邊的個數相等。

因此，當n為奇數時，S(Mn)是親切的。

綜上所述，對于一切的n≥2， Mobius梯的細分圖S(Mn)是親切圖。

下面給出n=3，4時，S(Mn)的親切標號:

參考文獻:

[1]Cahit I，Cordial graphs:a weaker version of graceful and harmonious graphs，Ars Combinatorics，1987，23，201-208.

[2]Joseph A.Gallian.A guide to the graph labeling zoo，Discrete Math，1994，(49).

[3]陳克波.關于Mobius梯的細分圖的k-優美性.海南師范學報(自然科學版).2002.6.

[4]陳福川.關于Mobius梯的細分圖的巧妙性.海南廣播電視大學學報. 2002.

[5]康慶德.圖標號問題[J].河北師范學院學報(自然科學版).1991，(1):102-115.