關于圖C4∪P3n的優美性

韋 芳, 吳躍生

(華東交通大學,11軌道交通學院; 2.基礎科學學院,江西南昌 330013)

關于圖C4∪P3n的優美性

韋 芳1, 吳躍生2

(華東交通大學,11軌道交通學院; 2.基礎科學學院,江西南昌 330013)

討論了形如C4∪非連通并圖的優美性,用構造性的方法給出了C4∪的優美標號,并證明C4∪P3n是交錯圖1

非連通圖; 優美標號; 優美圖; 交錯圖

1 引言與概念

本文所討論的圖均為無向簡單圖,V(G)和E(G)分別表示圖G的頂點集和邊集,未說明的符號及術語均同文[1].

定義1[2]在含有n個頂點的路Pn上,當且僅當兩點的距離為3時增加一條邊,所得到的圖叫做.

定義2[1]對于一個圖G=(V,E)如果存在一個單射θ:V(G)→{0,1,2,…,|E(G)|}使得對所有邊e =(u,v)∈E(G),由θ′(e)=|θ(u)-θ(v)|導出的E(G)→{1,2,…,|E(G)|}是一個雙射,則稱G是優美圖,θ是G的一組優美標號,稱θ′為G的邊上的由θ導出的誘導值.

定義3[6]G是一個優美二部圖,其優美標號為θ,V(G)劃分成兩個集合X,Y,如果則稱θ是G的交錯標號1稱G是在交錯標號θ下的交錯圖.

2 主要結果及其證明

定理 當nΕ4時,C4∪P3n是交錯圖.

證明:當nΕ4時,設圖C4∪P3n的頂點集如圖1所示.

圖1

圖2

圖3

圖4

圖5

圖6

圖7

[1]馬杰克.優美圖[M].北京:北京大學出版社,1991.

[2]林育青.關于圖P3n的優美性[J].華南師范大學學報(自然科學版),2000,(3):21-24.

[3]嚴謙泰,李武裝.關于圖P3n優美性的研究[J].數學的實踐與認識,2005,(4):131-139.

[4]王云,張秉儒.論圖P3n的優美性[J].電腦知識與技術,2007,(6):1661-1664.

[5]鄧懷敏,林育青.圖P3n的優美標號[J].新疆大學學報(自然科學版),2000,(2):12-16.

[6]付明彥,劉小冬,王力工.再論圖P3n的優美性[J].西南民族大學學報自然科學版,2007,(3):456-459.

[7]嚴謙泰.張忠輔.關于P3n的優美性[J].數學研究與評論,2004,24(2):89-92.

[8]吳躍生,毛國珍.關于圖C3∪P3n的優美性[J].懷化學院學報,2010,29(5):23-25.

Abstract:The gracefulnessof disconnected graphof C4∪P3nare discussed.The graceful labelings are given.It also proves that union graph of C4∪P3nare alternating graph.

Key words:disconnected graph; graceful labeling; graceful graph; alternating graph

On the Gracefulness of Graph C4∪P

WEI Fang1, WU Yue-sheng2
(1.School of Railway Tracks and Transportion; 2.School of Basic Science, East China Jiaotong University,Nanchang,Jiangxi 330013)

O157.5

A

1671-9743(2011)02-0023-03

2011-01-10

韋 芳(1963-),女,浙江東陽人,華東交通大學副教授,碩士,主要研究圖學.