【摘要】：圖論的二部圖及其標(biāo)號在實際應(yīng)用中較多,尤其最近圖標(biāo)號被應(yīng)用于新型的圖形密碼設(shè)計.首先構(gòu)造出了組合完全二部圖與串聯(lián)完全二部圖,發(fā)現(xiàn)了一種叫做奇邊魔幻全標(biāo)號的標(biāo)號,并給出了組合完全二部圖具有奇邊魔幻全標(biāo)號的證明.此外,得出了串聯(lián)完全二部圖是優(yōu)美圖、(k,d)-優(yōu)美圖的結(jié)論.
【圖文】：

Ｇ為（ｋ，ｄ）－優(yōu)美圖．定義３對于給定的（ｐ，ｑ）－圖Ｇ，如果存在一個映射ｆ：Ｖ（Ｇ）→［０，２ｑ－１］，使得圖Ｇ中任意兩個頂點ｘ、ｙ滿足ｆ（ｘ）≠ｆ（ｙ）且定義邊ｕｖ∈Ｅ（Ｇ）的標(biāo)號為ｆ（ｕｖ）＝ｆ（ｕ）＋ｆ（ｖ）．當(dāng)｛ｆ（ｕｖ）：ｕｖ∈Ｅ（Ｇ）｝＝［１，２ｑ－１］ｏ時，則稱ｆ為圖Ｇ的一個奇邊魔幻全標(biāo)號，圖Ｇ為奇邊魔幻圖．圖１是組合完全二部圖的示意圖，它由支架與完全二部圖組成，而支架是由頂點ａ１，ａ２，…，ａｓ依次連接，完全二部圖則是由圖Ｇｉ（ｉ∈［１，ｓ］）構(gòu)成，Ｇｉ即為Ｋｍ，ｎ．其中Ｖ（Ｇｉ）＝｛ａｉ，ｂｉ，ｔ，ｃｉ，ｋ｜ｔ∈［１，ｍ］，ｋ∈［１，ｎ］，ｉ∈［１，ｓ］｝，Ｅ（Ｇｉ）＝｛ａｉｂｉ，１，ｂｉ，ｔｃｉ，ｋ，ａｉａｉ＋１｜ｔ∈［１，ｍ］，ｋ∈［１，ｎ］，ｉ∈［１，ｓ］｝，再將每個完全二部圖Ｇｉ中的ａｉ（ｉ∈［１，ｓ］）相連．圖１一個組合完全二部圖Ｆｉｇ．１Ａｃｏｍｂｉｎａｔｏｒｉｃｃｏｍｐｌｅｔｅｂｉｐａｒｔｉｔｅｇｒａｐｈｓ圖２是串聯(lián)完全二部圖示意圖，它由ｎ個完全二部圖依次連接而成，完全二部圖則是由圖Ｇｉ構(gòu)成，Ｇｉ即為Ｋｍｉ，ｎｉ，其中Ｖ（Ｇｉ）＝｛ｂｉ，ｔｉ，ｃｉ

ｂｉ，ｔ，ｃｉ，，ｋ｜ｔ∈［１，ｍ］，ｋ∈［１，ｎ］，ｉ∈［１，ｓ］｝，Ｅ（Ｇｉ）＝｛ａｉｂｉ，１，ｂｉ，ｔｃｉ，ｋ，ａｉａｉ＋１｜ｔ∈［１，ｍ］，ｋ∈［１，ｎ］，ｉ∈［１，ｓ］｝，再將每個完全二部圖Ｇｉ中的ａｉ（ｉ∈［１，ｓ］）相連．圖１一個組合完全二部圖Ｆｉｇ．１Ａｃｏｍｂｉｎａｔｏｒｉｃｃｏｍｐｌｅｔｅｂｉｐａｒｔｉｔｅｇｒａｐｈｓ圖２是串聯(lián)完全二部圖示意圖，它由ｎ個完全二部圖依次連接而成，完全二部圖則是由圖Ｇｉ構(gòu)成，Ｇｉ即為Ｋｍｉ，ｎｉ，其中Ｖ（Ｇｉ）＝｛ｂｉ，ｔｉ，ｃｉ，ｋｉ｜ｉ∈［１，ｓ］，ｔｉ∈［１，ｍｉ］，ｋｉ∈［１，ｎｉ］｝，Ｅ（Ｇｉ）＝｛ｂｉ，ｔｉｃｉ，ｋｉ，ｂｉ，１ｃｉ－１，ｎ｜ｉ∈［１，ｓ］，ｔｉ∈［１，ｍｉ］，ｋｉ∈［１，ｎｉ］｝．圖２一個串聯(lián)完全二部圖Ｆｉｇ．２Ａｓｅｒｉｅｓｃｏｍｐｌｅｔｅｂｉｐａｒｔｉｔｅｇｒａｐｈｓ２主要結(jié)論定理１組合完全二部圖具有奇邊魔幻標(biāo)號．證明設(shè)圖Ｇ是組合完全二部圖，定義圖Ｇ的一個標(biāo)號ｆ：令ｆ（ｂ１，１）＝０．對ｉ∈［１，ｓ］，ｔ∈［１，ｍ］，ｋ∈［１，ｎ］分情形證明．若ｍ＝３，ｎ＝４．當(dāng)ｓ＝１時，有ｆ（ｂ１，２）＝８，ｆ（ｂ１
【作者單位】： 西北師范大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院;
【基金】：國家自然科學(xué)基金資助項目(61163037,61163054,61363060)
【分類號】：O157.5

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 胡琳,王國平;[2,3]-可選的完全二部圖的刻劃(英文)[J];新疆大學(xué)學(xué)報(自然科學(xué)版);2004年04期

2 賀佩玲;;完全二部圖k_(4,n)去掉兩條邊的交叉數(shù)[J];衡陽師范學(xué)院學(xué)報;2008年06期

3 賀佩玲;羅志軍;黃元秋;;幾個完全二部圖去掉一條邊的交叉數(shù)[J];河南師范大學(xué)學(xué)報(自然科學(xué)版);2011年02期

4 馮榮權(quán),金珠英;完全二部圖乘積上的Graham pebbling猜想[J];中國科學(xué)(A輯);2001年03期

5 王建,邱箏;｛P_4,C_4,S_4｝——分解[J];南通職業(yè)大學(xué)學(xué)報(綜合版);2001年04期

6 霍美霞;張欽峰;張淑芹;;完全二部圖的λ_4-最優(yōu)性[J];科學(xué)技術(shù)與工程;2008年07期

7 潘玉美;莫明忠;;完全二部圖全著色的構(gòu)造[J];廣西科學(xué)院學(xué)報;2010年01期

8 楊東;王井玉;;完全二部圖的鄰接譜(英文)[J];蘭州大學(xué)學(xué)報(自然科學(xué)版);2011年03期

9 陳綱;;蘊含K_(3,s)-ke的可圖序列[J];廣西科學(xué);2006年03期

10 陳祥恩;胡志濤;王治文;;完全二部圖K_(1,n),K_(2,n)和K_(3,n)的點強可區(qū)別全染色[J];數(shù)學(xué)的實踐與認(rèn)識;2012年11期

相關(guān)博士學(xué)位論文 前2條

1 劉鳳霞;完全二部圖的單色樹劃分和單色樹覆蓋[D];南開大學(xué);2009年

2 范文文;邊傳遞的完全二部圖及完全二部地圖[D];云南大學(xué);2014年

相關(guān)碩士學(xué)位論文 前10條

1 傅孟達(dá);完全二部圖K_(4,n)所有符號圖的準(zhǔn)虧格上界[D];湖南科技大學(xué);2015年

2 臧玉萍;匹配的anti-Ramsey染色[D];浙江師范大學(xué);2016年

3 劉婷婷;圖的3-彩虹指標(biāo)的相關(guān)研究[D];天津大學(xué);2015年

4 師瑾;若干完全二部圖的點可區(qū)別IE-全染色[D];西北師范大學(xué);2016年

5 張穎芳;完全二部圖K_（n，n）的循環(huán)圈分解及邊—平衡指數(shù)集[D];河南理工大學(xué);2009年

6 范文文;局部2-弧傳遞的完全二部圖[D];云南大學(xué);2011年

7 孔浩;圖的均勻（t，k，d）-樹染色[D];山東大學(xué);2011年

8 龍建軍;一些圖的[r,s,t]染色[D];福州大學(xué);2011年

9 胡志濤;圖的點強可區(qū)別全染色的研究[D];西北師范大學(xué);2013年

10 王井玉;若干圖的譜性質(zhì)研究[D];蘭州大學(xué);2010年

本文編號：2529267