論偶優(yōu)美圖與偶強協(xié)調圖

常慶龍,嚴謙泰

(1.江蘇省泰興教師進修學校，江蘇 泰興 225400;2.安陽師范學院 數(shù)學與統(tǒng)計學院，河南 安陽 455000)

?

論偶優(yōu)美圖與偶強協(xié)調圖

常慶龍1,嚴謙泰2

(1.江蘇省泰興教師進修學校，江蘇 泰興 225400;2.安陽師范學院 數(shù)學與統(tǒng)計學院，河南 安陽 455000)

給出了連通圖為偶優(yōu)美圖和偶強協(xié)調圖的充要條件，并對不連通的偶優(yōu)美性和偶強協(xié)調性進行了一些探討.

優(yōu)美圖；強協(xié)調圖；偶優(yōu)美圖；偶強協(xié)調圖

1 引言

1972年，Golomb明確給出了優(yōu)美圖的定義[1].1991年，Gnanajothi定義了奇優(yōu)美圖，并提出猜想：所有的樹都是奇優(yōu)美的[2].1982年，F(xiàn)rankHsu引入了強協(xié)調圖的概念[3].在此基礎上，2003年，王衛(wèi)軍，嚴謙泰又給出了奇強協(xié)調圖的概念[4].循此思路，2014年，吳躍生等也提出了偶優(yōu)美圖和偶強協(xié)調圖的概念[5].目前，國內關于偶優(yōu)美圖和偶強協(xié)調圖的研究尚屬于空白.本文給出一些初步結果，以期拋磚引玉.

本文涉及的圖均指有限、無向、簡單圖，通常用G表示一個圖，用V(G)、E(G)、|V(G)|、|E(G)|分別表示圖G的頂點集、邊集、頂點數(shù)、邊數(shù).并把有p個頂點q條邊的圖叫(p,q)圖.

定義1[1]對于(p,q)圖G，如果存在一個單射(— —映射)

使得對一切uv∈E(G),由θ' (uv)=|θ(u)-θ(v)|導出一個雙射(一一對應)

則稱θ是G的一個優(yōu)美標號(或優(yōu)美值)，稱G為優(yōu)美圖，θ'為G的邊標號.

定義2[6]設圖G是一個優(yōu)美圖，其優(yōu)美值為θ.如果存在V(G)的一個劃分(X,Y),使E(G)中的每條邊的兩端均分屬于X和Y，且滿足：

定義3[5]對于(p,q)圖G，如果存在一個單射

使得對一切uv∈E(G),由f' (uv)=|f(u)-f(v)| 導出一個雙射

則稱f為G的一個偶優(yōu)美標號，稱G為偶優(yōu)美圖.

定義4[3]對于(p,q)圖G，如果存在一個單射

使得對一切uv∈E(G),由φ' (uv)=φ(u)+φ(v) 導出一個雙射

則稱φ為G的一個強協(xié)調標號，稱G為強協(xié)調圖.

定義5[5]對于(p,q)圖G，如果存在一個單射

則稱h為G的一個偶強協(xié)調標號，稱G為偶強協(xié)調圖.

2 主要結果

定理1 任何優(yōu)美圖都是偶優(yōu)美圖.

證 設G是優(yōu)美圖，θ是其優(yōu)美標號，令f(v)=2θ(v),v∈V(G)，易知f即為G的偶優(yōu)美標號.

定理2 連通圖G為偶優(yōu)美圖的充要條件是G為優(yōu)美圖.

證 由定理1即知充分性成立.

設G為偶優(yōu)美圖且是連通的，易知G的偶優(yōu)美值均為偶數(shù)，只須將所有頂點的偶優(yōu)美值取其半，即得G的優(yōu)美值，必要性得證.

定理3 任一優(yōu)美圖與交錯圖的不交并是偶優(yōu)美圖.

證 設G1為優(yōu)美圖，其優(yōu)美標號為θ，|E(G)|=q1.G2為交錯圖，其交錯標號為h，|E(G)|=q2，X、Y分別為其小號點集和大號點集.

定義圖G1∪G2的頂點標號：

另一方面，由于

{f' (uv)|uv∈E(G2)}

={2(h(u)-h(v) )

+2q1|uv∈E(G2),v∈X,u∈Y}

所以

{f' (uv)|uv∈E(G1∪G2) }

因此

的雙射.

綜上，f是E(G1∪G2)的偶優(yōu)美標號，即G1∪G2是偶優(yōu)美圖.

定理4 任何強協(xié)調圖均為偶強協(xié)調圖.

證 (顯然).

定理5 連通圖為偶強協(xié)調圖的充要條件是其為強協(xié)調圖.

證 (顯然).

定理6 設(p,q)圖G為交錯圖，交錯數(shù)位m，則當n≥m時，圖G∪St(n)為偶強協(xié)調圖.

證 設G的交錯標號為θ，|E(G) |=q，V(St(n))={x0,x1,x2,…xn}，定義圖G∪St(n)的頂點標號f如下：

另一方面，由于

{f' (uv)│uv∈E(G),v∈X,u∈Y}

={2[q+n-(θ(u)-θ(v) ) ]

+2│uv∈E(G),v∈X,u∈Y}

所以，

f' (E(G∪St(n) ) )

由此可知f是G∪St(n)的偶強協(xié)調標號.

定理7 設G是強協(xié)調圖，則并圖G∪St(n)(n∈N+)是偶強協(xié)調圖.

證 設V(St(n) )={x0,x1,x2,…xn}，|E(G) |=q，G的強協(xié)調標號為θ.

若n≡1(mod2)，則定義G∪St(n)的頂點標號f如下：

f(v)=2θ(v)+n,v∈V(G)

若n≡0(mod2)，則定義f如下：

f(v)=2θ(v)+n-1,v∈V(G)

容易驗證f是G∪St(n)的偶強協(xié)調標號.

[1]S.W.Golomb.HowtonumberaGraphtheoryandcomputing.AcademicPrees,NewYork(1972),23-37.

[2]R.B.Gnanajothi.Topicsingraphtheory[D].Madurai:MaduraiKamarajUniversity,1991.

[3]FrankHsu.D.HarmoniousLabelingofWindmillgraph,JournalofGraphTheory. 1982,6(1),85-87.

[4]王衛(wèi)軍，嚴謙泰. 關于圖D_(m,4)的奇優(yōu)美性和奇強協(xié)調性[J]. 南陽師范學院學報(自然科學版)，2003,2(9):1-2.

[5]吳躍生，王廣富，徐保根. 交錯圖的奇優(yōu)美性和協(xié)調性. 武漢大學學報(理學版),2014,12(24):10-12.

[6]楊顯文. 關于C_(4,m)的優(yōu)美性[J]. 工程數(shù)學學報，1995(4)：108-112.

[責任編輯：張懷濤]

Study on Even Graceful and Even Strongly Harmonious Graphs

CHANG Qing-long1, YAN Qian-tai2

(1.Taixing Teacher’s Sraining School, Taixing 225400，China；2.School of Mathematics and Statistics, Anyang Normal University, Anyang 455000，China)

This paper gaves a necessary and sufficient condition of even graceful and even strongly harmonious graph for connected graphs. Even gracefulness and even strongly harmoniousness are studied for nonconnected graphs.

Graceful graphs; Strongly harmonious graph; Even graceful graph; Even strongly harmonious graph

2016-04-06

河南省自然科學基金(0511013800)；河南省教育廳自然科學基金(12A11003)

常慶龍，男，高級教師，主要研究組合排序與圖論;嚴謙泰(1964-),男，湖北武漢人，教授，主要從事圖論及其應用研究。

O

A

1671-5330(2016)05-0059-03