非連通圖的優(yōu)美標(biāo)號(hào)

吳躍生，王廣富

*吳躍生，王廣富

(華東交通大學(xué)基礎(chǔ)科學(xué)學(xué)院，江西 南昌 330013)

討論了非連通圖12(1,0,2,0,…,6,0)∪F,4的優(yōu)美性，證明了a,k,r(=1,2,…,6)，為任意自然數(shù)，且當(dāng)5=6=0，= 3，6=，5≥ 2-，=4；6≥ 4，= 5時(shí)，非連通圖12(1,0,2,0,…,6,0)∪F,4是交錯(cuò)圖。其中12(1,0,2,0,…,6,0)∪F,4表示圈12的(1,0,2,0,…,6,0)-冠，把順序有一個(gè)公共點(diǎn)的個(gè)4的連通并圖記作F,4。

優(yōu)美圖；非連通圖；平衡二分圖

1 引言與概念

圖的優(yōu)美標(biāo)號(hào)問題是組合數(shù)學(xué)中一個(gè)熱門課題[1- 18]。

顯然，若為的平衡標(biāo)號(hào)，則是邊導(dǎo)出標(biāo)號(hào)為1的邊的兩個(gè)端點(diǎn)中標(biāo)號(hào)較小的頂點(diǎn)的標(biāo)號(hào)。

把順序有一個(gè)公共點(diǎn)的個(gè)4的連通并圖記作F,4[1]。

文[3-6]研究了若干優(yōu)美圖的冠圖的優(yōu)美性，文[3]已經(jīng)指出：12(1,0,2,0,…,6,0)是優(yōu)美圖，文[7-18] 研究了一些非連通并圖的優(yōu)美性。本文討論了非連通圖12(1,0,2,0,…,6,0) ∪F,4的優(yōu)美性。

2 主要結(jié)果及其證明

圖1 圖Fm,4

定義非連通圖

的頂點(diǎn)標(biāo)號(hào)為：

下面證明

：(3,4)→[7, 17] ∪{1}是單射;

容易驗(yàn)證：

容易驗(yàn)證：

例1 根據(jù)定理1，非連通圖

的缺標(biāo)號(hào)值6的特征為10交錯(cuò)標(biāo)號(hào)，如圖2所示。

定義非連通圖

的頂點(diǎn)標(biāo)號(hào)為：

例2 根據(jù)定理2，非連通圖

缺標(biāo)號(hào)值6的特征為11交錯(cuò)標(biāo)號(hào)如圖3-5所示。

圖3 F4,4∪的交錯(cuò)標(biāo)號(hào)

圖4 F4,4∪的交錯(cuò)標(biāo)號(hào)

圖5 F4,4∪的交錯(cuò)標(biāo)號(hào)

定義非連通圖

的頂點(diǎn)標(biāo)號(hào)為：

例3 根據(jù)定理3，非連通圖

缺標(biāo)號(hào)值6的特征為12交錯(cuò)標(biāo)號(hào)如圖6-7所示。

圖6 的交錯(cuò)標(biāo)號(hào)

[1] 馬杰克.優(yōu)美圖[M]. 北京:北京大學(xué)出版社,1991.

[2] 楊顯文.關(guān)于C4m蛇的優(yōu)美性[J].工程數(shù)學(xué)學(xué)報(bào)，1995,12(4):108-112.

[3] Prabhahar Pradhan, Ajay Kumar, Debdas Mishra.On Gracefulness of Graphs Obtained from Hairy Cycles[J]. Journal of Combinatorics, Information & System Sciences ,2010, 35 (3-4):471-480.

[4] 吳躍生.關(guān)于圈C4h的(1,2,…,4h)-冠的優(yōu)美性[J].華東交通大學(xué)學(xué)報(bào),2011,28(1):77-80.

[5] 吳躍生, 李詠秋. 關(guān)于圈C4h+3的(1,2,…,4h+3)-冠的優(yōu)美性[J].吉首大學(xué)學(xué)報(bào):自然科學(xué)版,2011,32(6):1-4.

[6] 吳躍生, 王廣富. 關(guān)于C4h+1⊙1的(1,2,…,4h+1,4h+2)-冠的優(yōu)美性[J].山東大學(xué)學(xué)報(bào),2013, 48(4):25-27.

[7] 吳躍生. 關(guān)于圈C4h+3的(1,2,…,4h+3)-冠的優(yōu)美性[J].吉首大學(xué)學(xué)報(bào):自然科學(xué)版,2013,34(4): 1-6.

[9] 吳躍生.關(guān)于圖P6k+53∪Pn3的優(yōu)美性[J]. 吉首大學(xué)學(xué)報(bào):自然科學(xué)版,2012,33(3):4-7.

[10] 吳躍生.圖C7(1,2,3, ,4,5,0,0)∪St(m )的優(yōu)美性[J]. 吉首大學(xué)學(xué)報(bào):自然科學(xué)版,2012,33(5):9-1.

[11] 吳躍生, 王廣富, 徐保根. 非連通圖C2n+1∪G-1的優(yōu)美性[J].華東交通大學(xué)學(xué)報(bào), 2012,29(6):26-29.

[13] 魏麗俠，張昆龍.幾類并圖的優(yōu)美標(biāo)號(hào)[J].中山大學(xué)學(xué)報(bào):自然科學(xué)版,2008,47( 3):10-13.

[14] 蔡華，魏麗俠，呂顯瑞. 非連通圖(1∨P) ∪G和(1∨P) ∪(3∨K)及W∪()的優(yōu)美性[J].吉林大學(xué)學(xué)報(bào):理學(xué)版,2007, 45( 4):539-543.

[15] 蔡華.幾類非連通圖的優(yōu)美性[D]. 長(zhǎng)春：吉林大學(xué),2007.

[16] 張家娟，郭珠霞，周向前,等.優(yōu)美圖的一些性質(zhì)[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí), 2012, 42(13):197-201.

[18] Gallian J A. A Dynamic Survey of Graph Labeling[J]. The Electronic Journal of Combinatorics，2012,19:DS6.

The graceful labeling of the unconnected graph12(1,0,2,0,…,6,0)∪F,4

*WU Yue-sheng，WANG Guang-fu

(School of Basic Science, East China Jiaotong University, Nanchang, Jiangxi 330013, China)

The gracefulness of the unconnected graph12(1,0,2,0,…,6,0)∪F,4is discussed. Furthermore, we prove the following results: For any natural number a,k,r(=1,2,…,6)，if5=6=0，= 3，6=，5≥ 2-，=4；6≥ 4，= 5, then the unconnected graphs12(1,0,2,0,…,6,0)∪F,4are balanced bipartite graph.

graceful graph; unconnected graph; balanced bipartite graph

O159.1

A

10.3969/j.issn.1674-8085.2013.06.001

1674-8085(2013)06-0001-05

2013-09-22；

2013-10-12

國(guó)家自然科學(xué)基金項(xiàng)目(11261019，11361024) ; 江西省自然科學(xué)基金項(xiàng)目(20114BAB201010)

*吳躍生(1959-)，男，江西瑞金人，副教授，碩士，主要從事圖論研究(E-mail:616100567@qq.com);

王廣富(1976-)，男，山東荷澤人，副教授，博士，主要從事圖論研究(E-mail:wgfmath@126.com).