亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        P2×Cn的友好標(biāo)號集

        2013-12-19 03:54:14尤永旦
        關(guān)鍵詞:斷言小圈標(biāo)號

        尤永旦 華 波

        (1.浙江師范大學(xué) 數(shù)理與信息工程學(xué)院,浙江 金華321004;2.東華大學(xué) 理學(xué)院,上海201620)

        0 引言

        設(shè)圖G是一個簡單圖,由點的標(biāo)號函數(shù)f:V→Z2,可以誘導(dǎo)出邊的標(biāo)號函數(shù)f*:E→Z2,使得f*xy=fx+fymod2,?xy∈EG.對任意一個i∈Z2,定義vfi=f-1i和efi=f*-1i.如果vf1-vf0≤1,稱標(biāo)號函數(shù)f:V→Z2為友好標(biāo)號函數(shù).我們定義友好指數(shù)FI和全友好指數(shù)FFI指數(shù)如下:

        FIG=ef1-ef0f是圖G的一個友好標(biāo)號函數(shù),

        1 預(yù)備知識

        定義1.1[1]:給定兩個圖G=V,E和H=V',E',定義G×H=V×V',E''如下:

        E''=v,v',u,u':v.u∈E且v'=u'或者v=u且v'.u'∈E'.

        引理1.1[2]:Cm中有i個頂點賦值為1,不妨設(shè)1≤2i≤m,用參考文獻(xiàn)[2]求解的方法可知ef1可以取2,4,…,2i.此處的f未必是友好標(biāo)號函數(shù).

        引理1.2:設(shè)f是P2×Cn的一個友好標(biāo)號函數(shù),當(dāng)n=2k時候,ef1為偶數(shù),反之,ef1為奇數(shù).

        證明:i,j邊有兩個頂點:一個賦值為i另外一個賦值為j,i,j∈0,1.由引理1.1可知P2×Cn中的兩個圈Cn的ef1為偶數(shù)只要證明兩個圈Cn之間的邊ef1的奇偶性就行.現(xiàn)在考慮設(shè)兩個圈Cn之間的邊ef1的奇偶性,設(shè)在其中一個圈Cn中點賦值為1有i,其中2i≤n,在這個Cn中點賦值為0有n-i,在另外一個圈Cn中點賦值為1有n-i,并且點賦值為0有i,設(shè)兩圈之間有j條1,1邊其中j≤mini,n-i,則就會也有j條0,0邊,所以在這個兩個圈之間的0,1邊的邊數(shù)為n-2j,所以引理1.2成立.

        引理1.3:

        當(dāng)n≡0mod4時,F(xiàn)IP2×Cn?3n,3n-4,…,8,4,0,

        當(dāng)n≡2mod4時,F(xiàn)IP2×Cn?3n,3n-4,…,10,6,2,當(dāng)n=2k+1時,F(xiàn)IP2×Cn?3n,3n-2,…,5,3,1.

        證明:顯然ef1+ef0=EP2×Cn=3n.

        因此得知當(dāng)n≡0mod4時,F(xiàn)IP2×Cn?3n,3n-4,…,8,4,0,

        當(dāng)n≡2mod4時,F(xiàn)IP2×Cn?3n,3n-4,…,10,6,2,

        根據(jù)引理1.2,當(dāng)n=2k+1時候,ef1為奇數(shù),同理可知當(dāng)n≡2k+1,F(xiàn)IP2×Cn?3n,3n-2,…,5,3,1.

        2 主要結(jié)果

        定理2.1:

        當(dāng)n≡0mod4時,F(xiàn)IP2×Cn=3n,3n-8,3n-12,…,8,4,0,

        當(dāng)n≡2mod4時,F(xiàn)IP2×Cn=3n,3n-8,3n-12,…,10,6,2當(dāng)n=2k+1時,F(xiàn)IP2×Cn=3n-4,3n-8,3n-10,3n-12…,5,3,1.

        證明:

        若n=2j,由引理1.2可知在圖P2×Cn中ef1為偶數(shù).當(dāng)f是友好標(biāo)號函數(shù)時,則在圖P2×Cn中ef1為偶數(shù).且可證ef1取到大部分偶數(shù),證明如下:

        構(gòu)造使得ef1=4的友好標(biāo)號函數(shù)

        構(gòu)造使得ef1=3n的友好標(biāo)號函數(shù)

        e1可取到4,6,8,…,2n-2,2n,3n,

        可證P2×Cn中ef1≠2.

        若有兩個圈C1=u1,1u1,2u1,3…u1,n,C2=u2,1u2,2u2,3…u2,n的邊賦值都為0,則根據(jù)友好標(biāo)號函數(shù)可知兩個圈的點賦值一個賦值為0,另外一個賦值為1,則ef1=n≥4,若有一個圈(不妨設(shè)為C1=u1,1u1,2u1,3…u1,n)中有邊賦值為1,因為圈邊賦值為1為偶數(shù)所以這個圈中邊賦值至少為偶數(shù),又根據(jù)友好標(biāo)號函數(shù),則在另外一個圈中必然也是邊賦值1的條也是偶數(shù)并且在這個圈中ef1≥2,所以在P2×Cn中ef1≠2.

        又可證P2×Cn中ef0≠2.

        第一種情形若ef0=2的邊全在圈C1中,則邊賦值為0的邊(不妨設(shè)邊u1,iu1,i+1)必然與下面一個圈C2中u2,i,u2,i+1兩點組成一個小圈,則可得出在這個小圈中ef0=2或者4.同理在另外一個小圈ef0=2或者4,則就會出現(xiàn)ef0≠2,假設(shè)矛盾.

        第二種情形ef0=2都不在圈C1,C2中不妨設(shè)邊u1,iu2,i,u1,ju2,j,1+i≤j為1,圈C3=u1,iu2,iu2,i-1u1,i-1這樣可知道是在圈C3,圈C4與圈C5=u1,iu2,iu2,i+1…u

        2,ju1,ju1,j-1u1,j-2…u1,i+1,1+i≤j中每個圈的ef0至少為2,所以得出ef0≠2與假設(shè)矛盾.因為

        ef1≠2,ef0≠2可知3n-4?FIP2×Cn.因為e1=4,6,8,…,2n-2,2n,3n,e1≠2,e0≠2,再根據(jù)根據(jù)引理1.3,所以當(dāng)n≡2mod4時,F(xiàn)IP2×Cn=3n,3n-8,3n-12,…,8,4,0.

        當(dāng)n≡2mod4時,F(xiàn)IP2×Cn=3n,3n-8,3n-12,…,10,6,2.

        斷言1:若n=2j+1,則在圖P2×Cn中ef1為取到大部分奇數(shù).證明如下:

        由引理1.2在圖P2×Cn中e1為奇數(shù),構(gòu)造使得ef1=5的友好標(biāo)號函數(shù)

        構(gòu)造使得ef1=7的友好標(biāo)號函數(shù)

        現(xiàn)在已經(jīng)構(gòu)造友好標(biāo)號函數(shù)使得e1=5,7,…,2n+1,

        這樣就有ef0=2,4,…,n-1,根據(jù)ef1+ef0=EP2×Cn=3n,可知ef1=3n-2,3n-4,…,2n+1,所以我們已經(jīng)構(gòu)造出ef1=5,7,…,2n+1,…,3n-4,3n-2.

        斷言2:ef1≠1,其中f為P2×Cn的友好標(biāo)號函數(shù).

        若在P2×Cn中ef1=1,邊賦值為1在下面C1=u1,1u1,2u1,3…u1,n,C2=u2,1u2,2u2,3…u2,n中的某個圈中,不妨設(shè)C1=u1,1u1,2u1,3…u1,n,則根據(jù)引理1.1可知邊賦值為1至少兩條,與假設(shè)矛盾,若都不在這兩個圈C1=u1,1u1,2u1,3…u1,n,C2=u2,1u2,2u2,3…u2,n,則邊賦值為1在圈C1與圈C2之間的連接處,不妨設(shè)點u1,1=0,u2,1=1,則在C3=u1,1u2,1u2,2u1,2中,根據(jù)引理2.1可知邊賦值為1至少兩條,所以P2×Cn中ef1≠1.

        斷言3:當(dāng)n≥5時,ef1≠3,其中f為P2×Cn的友好標(biāo)號函數(shù).

        若有兩個圈C1=u1,1u1,2u1,3…u1,n,C2=u2,1u2,2u2,3…u2,n邊賦值為都為0,則根據(jù)友好標(biāo)號函數(shù)可知C1=u1,1u1,2u1,3…u1,n的點都賦值為0,C2=u2,1u2,2u2,3…u2,n的點都賦值為1;或者C1=u1,1u1,2u1,3…u1,n的點都賦值為1,C2=u2,1u2,2u2,3…u2,n的點都賦值為0,則e1=n≥5.

        若有一個圈C1=u1,1u1,2u1,3…u1,n中邊賦值為1,根據(jù)引理1.1可知圈邊賦值為1的邊數(shù)為偶數(shù),所以在這個圈C1中ef1≥2,又根據(jù)友好標(biāo)號函數(shù),則在C2=u2,1u2,2u2,3…u2,n中必然也是邊賦值1且為偶數(shù)條,而且在這個圈C2中ef1≥2,所以ef1≥4≠3.

        斷言4:ef0≠1ef0≠3,其中f為P2×Cn的友好標(biāo)號函數(shù).

        因為由引理1.2可知e1為奇數(shù),所以可知在該圖中e0為偶數(shù),所以e0≠1e0≠3明顯成立.

        當(dāng)n=2k+3時,k∈1,2,3,…,因為e1=5,7,9,…,2n-7,…,3n-2,

        e1≠3,e0≠3,e1≠1,e0≠1,顯然這個等式e1=3n不成立(由引理1.1可知在奇圈中e1也是偶數(shù)而e1=3n這個是奇數(shù)).

        當(dāng)n=2k+3,n∈1,2,3,…時,F(xiàn)IP2×Cn=3n-4,3n-8,3n-10,3n-12…,5,3,1.

        當(dāng)n=3時,ef1≠1,ef1≠3n=9,ef1=3,5,7,所以FIP2×C3=5,3,1.

        所以當(dāng)n=2k+1時,F(xiàn)IP2×Cn=3n-4,3n-8,3n-10,3n-12…,5,3,1.

        參考文獻(xiàn):

        [1]J A Bandy, U S R Murty.Graph Theory with Application[M].Springer International Publisher,2007.

        [2] N Cairnie , K Edwards.The computational complexity of cordial and equitable labeling[J].Discrete Math,2000,216:29-34.

        Abstract: Friendly index set is a common problem in the labeling problem. The present paper researches the friendly index set of graphP2×Cn.

        Keywords:friendly labeling function; FI; FFI; circle

        猜你喜歡
        斷言小圈標(biāo)號
        von Neumann 代數(shù)上保持混合三重η-*-積的非線性映射
        C3-和C4-臨界連通圖的結(jié)構(gòu)
        特征為2的素*-代數(shù)上強保持2-新積
        Top Republic of Korea's animal rights group slammed for destroying dogs
        米小圈小漫畫
        米小圈
        非連通圖2D3,4∪G的優(yōu)美標(biāo)號
        米小圈小漫畫
        非連通圖D3,4∪G的優(yōu)美標(biāo)號
        非連通圖(P1∨Pm)∪C4n∪P2的優(yōu)美性
        日韩亚洲精品中文字幕在线观看 | 亚洲二区三区在线播放| 国产精品国产三级国产an不卡| 国产精品无码翘臀在线观看| 欧美最大胆的西西人体44| 亚洲成人电影在线观看精品国产 | 国产精品国产三级国产an| 国产精品成人一区二区在线不卡| 18岁日韩内射颜射午夜久久成人| 中国丰满熟妇av| 国产精品美女黄色av| 色 综合 欧美 亚洲 国产| 9191在线亚洲精品| av免费看网站在线观看| 亚洲国产美女高潮久久久| 亚洲日韩一区二区一无码| 国产美女久久精品香蕉69| 久久精品一品道久久精品9 | 亚洲综合在线观看一区二区三区 | 丰满人妻熟妇乱又伦精品软件| 久久青草免费视频| 国产精品黄页免费高清在线观看| 日韩有码中文字幕在线视频| 亚洲成av人片乱码色午夜| 亚洲国产精品嫩草影院久久| 一本一道AⅤ无码中文字幕| 丝袜美腿在线观看视频| 国产乱人偷精品人妻a片| 精品无码国产污污污免费网站| 91自国产精品中文字幕| av天堂最新在线播放| 人妻无码一区二区视频| 精品欧美久久99久久久另类专区| 亚洲无人区一码二码国产内射 | 男女性搞视频网站免费| 开心五月婷婷激情综合网| 久久久久久久久蜜桃| 精品一区二区三区免费爱| 日韩有码中文字幕在线视频| 亚洲欧美日韩精品久久| 亚洲AV无码一区二区三区人|