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

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

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

【相似文獻】

相關期刊論文 前10條

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

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

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

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

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

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

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

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

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

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

相關博士學位論文 前2條

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

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

相關碩士學位論文 前10條

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

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

3 劉婷婷;圖的3-彩虹指標的相關研究[D];天津大學;2015年

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

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

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

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

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

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

10 王井玉;若干圖的譜性質研究[D];蘭州大學;2010年

本文編號：2529267