• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

    再探非連通圖C4m-1∪G的優(yōu)美標(biāo)號

    2016-01-08 02:09:20吳躍生

    再探非連通圖C4m-1∪G的優(yōu)美標(biāo)號*

    吳躍生

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

    摘要:討論了非連通圖C4m-1∪G的優(yōu)美性,給出了非連通圖C4m-1∪G是優(yōu)美圖的2個充分條件.

    關(guān)鍵詞:優(yōu)美圖;交錯圖;非連通圖;優(yōu)美標(biāo)號

    文章編號:1007-2985(2015)01-0001-04

    中圖分類號:O157.5文獻標(biāo)志碼:A

    DOI:10.3969/j.issn.1007-2985.2015.01.001

    收稿日期:*2014-05-27

    基金項目:國家自然科學(xué)基金資助項目(11261019,11361024);江西省自然科學(xué)基金資助項目(20114BAB201010)

    作者簡介:吳躍生(1959—),男,江西瑞金人,華東交通大學(xué)基礎(chǔ)科學(xué)學(xué)院副教授,碩士,主要從事圖論研究.

    1相關(guān)定義

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

    文中所討論的圖均為無向簡單圖,V(G)和E(G)分別表示圖G的頂點集和邊集,記號[m,n]表示整數(shù)集合{m,m+1,…,n},其中m和n均為非負整數(shù),且滿足0≤m

    定義1對于一個圖G=(V,E),若存在一個單射θ:V(G)→[,|E(G)|]使得對所有邊e=(u,v)∈E(G),由θ′(e)=|θ(u)-θ(v)|導(dǎo)出的E(G)→[1,|E(G)|]一個雙射,則稱G是優(yōu)美圖,θ是G的一組優(yōu)美標(biāo)號,稱θ′為G的邊上的由θ導(dǎo)出的誘導(dǎo)值.

    文獻[12]中討論了非連通圖C4m-1∪G的優(yōu)美性,給出了非連通圖C4m-1∪G是優(yōu)美圖的2個充分條件:對任意正整數(shù)m,若圖G是特征為k且缺k+3m-1標(biāo)號值的交錯圖(3m-1≤k+3m-1≤|E(G)|),則非連通圖C4m-1∪G存在缺標(biāo)號值k+1的優(yōu)美標(biāo)號;對任意正整數(shù)m,若圖G是特征為k且缺k+m+1標(biāo)號值的交錯圖(m+1≤k+m+1≤|E(G)|),則非連通圖C4m-1∪G存在缺標(biāo)號值k+1的優(yōu)美標(biāo)號.文獻[13]中討論了非連通圖D2,8∪G的優(yōu)美性.

    筆者繼續(xù)討論非連通圖C4m-1∪G的優(yōu)美性.

    定義2設(shè)f為G的一個優(yōu)美標(biāo)號,若存在一個正整數(shù)k,使得對?uv∈E(G)有f(u)>k≥f(v)或f(u)≤k

    顯然,若f為G的平衡標(biāo)號,則k是邊導(dǎo)出標(biāo)號為1的邊的2個端點中標(biāo)號較小的頂點的標(biāo)號.

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

    定理1對任意正整數(shù)m,若圖G是特征為k且缺k+3m-2標(biāo)號值的交錯圖(3m-2≤k+3m-2≤|E(G)|),則非連通圖C4m-1∪G存在缺標(biāo)號值k+4m-1的優(yōu)美標(biāo)號.

    定義C4m-1∪G的頂點標(biāo)號θ為:

    θ(x2i)=4m-i+k-1,i=1,2,…,2m-1;θ(x2i-1)=i+k,i=1,2,…,m;

    下面證明θ是非連通圖C4m-1∪G的優(yōu)美標(biāo)號.

    (ⅰ)θ:X→[0,k]是單射(或雙射);θ:Y→[k+4m,q+4m-1]-{7m-3+k}是單射(或雙射);θ:V(C4m-1)→[k+1,k+4m-2]∪{7m-3+k}是單射(或雙射);θ:V(C4m-1∪G)→[0,q+4m-]-{k+4m-1}是單射.

    (ⅱ)

    θ′(x 2m+2x 2m+1)=4m-1;

    θ′(x2mx2m+1)=4m-2;θ′(x4m-1x1)=2m-2.

    θ′:E(C4m-1)→[1,4m-1]是雙射;θ′:E(G)→[4m,q+4m-1]是雙射.θ′:E(C4m-1∪G)→[1,q+4m-1]是一一對應(yīng).

    由(ⅰ)和(ⅱ)可知,θ就是非連通圖C4m-1∪G的缺k+4m-1標(biāo)號值的優(yōu)美標(biāo)號.證畢.

    定理2對任意正整數(shù)m,若圖G是特征為k且缺k+m標(biāo)號值的交錯圖(m≤k+m≤|E(G)|),則非連通圖C4m-1∪G存在缺標(biāo)號值k+4m-1的優(yōu)美標(biāo)號.

    定義C4m-1∪G的頂點標(biāo)號θ為:

    θ(x2i)=4m-i+k-1,i=1,2,…,m-1;

    θ(x2m)=k+5m-1,θ(x2i)=4m-i+k,i=m+1,m+2,…,2m-1;

    下面證明θ是非連通圖C4m-1∪G的優(yōu)美標(biāo)號.

    (ⅰ)θ:X→[0,k]是單射(或雙射);θ:Y→[k+4m,q+4m-1]-{k+5m-1}是單射(或雙射);θ:V(C4m-1)→[k+1,k+4m-2]∪{k+5m-1}是單射(或雙射);θ:V(C4m-1∪G)→[0,q+4m-1]-{k+4m-1}是單射.

    (ⅱ)

    θ′(x 2m-1x 2m)=4m-1;

    θ′(x2mx2m+1)=4m-2;θ′(x4m-1x1)=2m-1.

    由(ⅰ)和(ⅱ)可知θ就是非連通圖C4m-1∪G的缺k+4m-1標(biāo)號值的優(yōu)美標(biāo)號.證畢.

    定義4[4-7]V(G)= {u1,u2,…,un}的每個頂點ui都粘接了ri條懸掛邊(ri為自然數(shù),i=1,2,…,n)所得到的圖,稱為圖G的(r1,r2,…,rn)-冠,簡記為 G(r1,r2,…,rn).特別地,當(dāng)r1=r2=… =rn=r時,稱為圖G的r-冠.圖G的0-冠就是圖G.

    引理1對任意正整數(shù)m,任意自然數(shù)r1,r2,…,rm,C4m(r1,0,r2,0,…,rm,0,…,0)存在特征為2m-1,且缺3m的交錯標(biāo)號.

    注意到3m=(2m-1)+m+1,由定理1和引理1有以下結(jié)論:

    推論1對任意正整數(shù)m(m≥2),任意自然數(shù)r1,r2,…,r3m-3,非連通圖C4m-1∪C12m-12(r1,0,r2,0,…,r3m-3,0,…,0)存在缺標(biāo)號值10m-8的優(yōu)美標(biāo)號.

    例1當(dāng)m=2,r1=r2=r3=0時,由推論1給出的非連通圖C7∪C12存在缺標(biāo)號值12的優(yōu)美標(biāo)號為:

    C7:6,11,7,10,16,9,8;

    C12:0,19,1,18,2,17,3,15,4,14,5,13.

    當(dāng)m=2,r1=1,r2=2,r3=3時,由推論1給出的非連通圖C7∪C12(1,0,2,0,3,0,0,…,0)存在缺標(biāo)號值12的優(yōu)美標(biāo)號為:

    C7:6,11,7,10,16,9,8;

    C12(1,0,2,0,3,0,0,…,0):0(25),24,1(23,22),21,2(20,19,18),17,3,15,4,14,5,13.

    由定理2和引理1有以下結(jié)論:

    推論2對任意正整數(shù)m,任意自然數(shù)r1,r2,…,rm-1,非連通圖C4m-1∪C4m-4(r1,0,r2,0,…,rm-1,0,…,0)存在缺6m-4標(biāo)號值的優(yōu)美標(biāo)號.

    例2當(dāng)m=3,r1=r2=0時,由推論2給出的非連通圖C11∪C8的缺標(biāo)號值14的優(yōu)美標(biāo)號為:

    C11:4,13,5,12,6,17,7,11,8,10,9;

    C8:0,19,1,18,2,16,3,15.

    當(dāng)m=3,r1=8,r2=9時,由推論2給出的非連通圖C11∪C8(8,0,9,0,0,0,0,0)的缺標(biāo)號值14的優(yōu)美標(biāo)號為:

    C11:4,13,5,12,6,17,7,11,8,10,9;

    C8(8,0,9,0,0,0,0,0):0(36,35,34,33,32,31,30,29),28,1(27,26,25,24,23,22,21,20,19),18,2,16,3,15.

    引理2[10]對任意自然數(shù)n,當(dāng)n≥2時,C2n+1是有2n+1個頂點的圈,Gn-1是邊數(shù)為n-1的優(yōu)美圖,則非連通圖C2n+1∪Gn-1是優(yōu)美的.

    因為E(C4m-1)=4m-1,所以由引理2有以下結(jié)論:

    推論3設(shè)m為任意的正整數(shù),則非連通圖C4m-1∪C2(4m)+1是優(yōu)美的.

    因為E(C4m-1∪C12m-12(r1,0,r2,0,…,r3m-3))=16m-13+r1+r2+…+r3m-3,令16m-13+r1+r2+…+r3m-3=a,所以由推論1和引理2有以下結(jié)論:

    推論4對任意正整數(shù)m(m≥2),任意自然數(shù)r1,r2,…,r3m-3,非連通圖C4m-1∪C12m-12(r1,0,r2,0,…,r3m-3,0,…,0)∪C2(a+1)+1是優(yōu)美的.

    因為E(C4m-1∪C4m-4(r1,0,r2,0,…,rm-1))=8m-5+r1+r2+…+rm-1,令8m-5+r1+r2+…+rm-1=b,所以由推論2和引理2有以下結(jié)論:

    推論5對任意正整數(shù)m(m≥2)和任意自然數(shù)r1,r2,…,rm-1,非連通圖C4m-1∪C4m-4(r1,0,r2,0,…,rm-1,0,…,0)∪C2(b+1)+1是優(yōu)美的.

    參考文獻:

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

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

    [3]吳躍生.關(guān)于圈C4h的(r1,r2,…,r4h)-冠的優(yōu)美性.華東交通大學(xué)學(xué)報,2011,28(1):77-80.

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

    [7]吳躍生.圖C7(r1,r2,r3,r4,r5,0,0)∪St(m)的優(yōu)美性.吉首大學(xué)學(xué)報:自然科學(xué)版,2012,33(5):9-11;25.

    [8]吳躍生,王廣富,徐保根.關(guān)于C4h+1⊙K1的(Gr1,Gr2,…,Gr4h+1,Gr4h+2)-冠的優(yōu)美性.山東大學(xué)學(xué)報,2013,48(4):25-27.

    [9]吳躍生.關(guān)于圈C4h+3的(Gr1,Gr2,…,Gr4h+3)-冠的優(yōu)美性.吉首大學(xué)學(xué)報:自然科學(xué)版,2013,34(4):4-9.

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

    [11] GALLIAN J A.A Dynamic Survey of Graph Labeling.The Electronic Joumal of Combinatorics,2013,16(DS6):1-308.

    [12] 吳躍生.非連通圖C4m-1∪G的優(yōu)美標(biāo)號.吉首大學(xué)學(xué)報:自然科學(xué)版,2014,35(3):1-3.

    [13] 吳躍生.非連通圖D2,8∪G的優(yōu)美性.西華師范大學(xué)學(xué)報:自然科學(xué)版,2014:35(1):4-6.

    [14] 吳躍生.非連通圖G+e∪Hk-1的優(yōu)美性.吉首大學(xué)學(xué)報:自然科學(xué)版,2014,35(2):3-5.

    [15] 賈慧羨,左大偉.與扇圖相關(guān)的2類圖的超邊優(yōu)美標(biāo)號.吉首大學(xué)學(xué)報:自然科學(xué)版,2014,35(2):6-9.

    Revisiting the Graceful Labeling of the Unconnected GraphC4m-1∪G

    WU Yuesheng

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

    Abstract:The gracefulness of the unconnected graph C4m-1∪G is discussed.Two sufficient conditions are given for the gracefulness of unconnected graph C4m-1∪G.

    Key words:graceful graph;balanced bipartite graph;unconnected graph;graceful labeling

    (責(zé)任編輯向陽潔)

    株洲市| 吉首市| 绍兴县| 京山县| 腾冲县| 伊吾县| 启东市| 临泉县| 平乐县| 苏尼特左旗| 娄底市| 福清市| 湖南省| 安义县| 进贤县| 上饶市| 奉新县| 嘉祥县| 洪泽县| 陆川县| 巴林左旗| 洛阳市| 新昌县| 罗甸县| 准格尔旗| 布拖县| 新巴尔虎右旗| 唐山市| 郑州市| 晋中市| 桑日县| 镶黄旗| 嘉鱼县| 大姚县| 崇文区| 老河口市| 民和| 拜城县| 静安区| 湄潭县| 大港区|