鄰點
- 若干倍圖的鄰點全和可區(qū)別全染色
將任意一點的所有鄰點顏色加入其全染色權(quán)重和中,提出了圖的鄰點全和可區(qū)別全染色的概念[5].注意到,Flandrin等在文獻[5]中僅將圖的鄰點全和可區(qū)別全染色與鄰點被擴展和可區(qū)別全染色作了一個簡單的對比,并未進行深入研究.近年來,圖的鄰點全和可區(qū)別全染色在文獻[6-7]中被進一步研究.受此啟發(fā),本文研究路、圈、星、扇、輪、完全二部圖以及樹的倍圖的鄰點全和可區(qū)別全染色問題．1 預(yù)備知識本文涉及的圖均為連通的簡單圖,V(G)和E(G)分別表示圖G的點集和邊集,
華中師范大學(xué)學(xué)報（自然科學(xué)版） 2023年5期2023-10-16
- Kn□Km,s的r-hued染色
r,故viu1的鄰點集至少可染r種不同顏色, 由于viu1在Kn中, 所以滿足正常染色時該點鄰點在X中已有(n-1)種不同顏色, 因此在Y中的鄰點至少有(r-n+1)種顏色.用W1,W2,…,Wr-n+1,…,Ws表示Kn在Kn□Km,s中Y部分的第1,2,3,…,r-n+1,…,s個拷貝, 于是可任意調(diào)整順序, 不妨設(shè)前(r-n+1)個是用來滿足X中頂點條件(ii)的.對于X中第一列頂點, 由于在Kn中, 不妨設(shè)染色為c(viu1)=i(1≤i≤n),
吉林大學(xué)學(xué)報（理學(xué)版） 2023年1期2023-03-09
- 路和圈、圈和圈的Kronecker 積圖的超點連通性?
點割都是某個點的鄰點集,那么G 是超點連通的,或者簡稱為是super-κ 的.由定義可知,若圖G 是超點連通的,則G 一定是極大點連通的;反過來不一定成立,比如對于整數(shù)k ≥3,C2k是極大點連通的但不是超點連通的.圖G1與G2的Kronecker 積圖是一個點集為V(G1×G2)=V(G1)×V(G2),邊集為E(G1×G2)={(u1,v1)(u2,v2):u1u2∈E(G1),v1v2∈E(G2)} 的圖.文獻[2] 研究了兩個完全圖的Kroneck
- 關(guān)于圖Pa,b的鄰點可區(qū)別染色
別邊染色[1]、鄰點可區(qū)別邊染色[2-6]、鄰點可區(qū)別全染色[7]、鄰點強可區(qū)別全染色[8]等染色法，這些都是十分困難的問題，至今文獻甚少。文中將通過具體的染色方法，給出圖Pa,b的鄰點可區(qū)別邊染色數(shù)、鄰點可區(qū)別全染色數(shù)、鄰點強可區(qū)別全染色數(shù)。定義2[7]圖G(V,E)的一個正常全染色f:V∪E→{1,2,…,k}，如果滿足：1)對任意的uv∈E有f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv);2)對任意的uv,vw∈E有f(uv)≠f(v
安陽師范學(xué)院學(xué)報 2022年5期2022-11-04
- 無相鄰3-圈平面圖的鄰點可區(qū)別邊染色
002年提出圖的鄰點可區(qū)別邊染色這一概念,并對一些特殊圖類(樹、路、圈、完全圖、完全二部圖等)的鄰點可區(qū)別邊色數(shù)進行了刻畫.基于這些結(jié)果,他們給出了關(guān)于圖的鄰點可區(qū)別邊染色問題的猜想.1 定理1的證明假設(shè)G是定理1中關(guān)于邊數(shù)達到最小的一個極小反例.顯然,G是連通的.先分析G的結(jié)構(gòu)性質(zhì),再運用權(quán)轉(zhuǎn)移方法得出矛盾,從而定理1得證.令T(G)=max{10,Δ(G)+2},C={1,2,…,T(G)}表示顏色集合.顯然|C|≥10.斷言1[15]圖G中1-點不與
浙江師范大學(xué)學(xué)報（自然科學(xué)版） 2022年4期2022-10-28
- 廣義Mycielski圖Mn(Pt)的鄰點可區(qū)別的I-均勻全染色
文獻[4]提出了鄰點可區(qū)別I-全染色的概念.文獻[5]給出了鄰點可區(qū)別I-均勻全染色的概念和鄰點可區(qū)別I-均勻全染色猜想.文獻[10]給出了若干Mycielski圖的鄰點可區(qū)別I-均勻全染色.本文根據(jù)路的第一類廣義Mycielski圖的構(gòu)造特征,運用函數(shù)構(gòu)造法研究并確立了這類圖鄰點可區(qū)別I-均勻全色數(shù).特別的,當t>3時，針對路的第一類廣義Mycielski圖Mn(Pt),根據(jù)n的取值分5種情況討論并給出了其鄰點可區(qū)別的I-均勻全色數(shù), 所得結(jié)果驗證了這類
蘭州文理學(xué)院學(xué)報(自然科學(xué)版) 2022年3期2022-06-08
- 兩類圖的鄰點可區(qū)別全染色
[1]首先提出了鄰點可區(qū)別全染色的定義，并確定了圈、完全圖、扇、輪、完全二部圖、路、樹的鄰點可區(qū)別全色數(shù).從此鄰點可區(qū)別全染色得到了很多人的重視，但由于缺乏一個系統(tǒng)而有效的研究方法，至今大部分的成果都是針對一些特殊圖去探索其鄰點可區(qū)別全染色，也取得了一些研究成果[1-21].本文主要研究了輪環(huán)圖kCn和圖k×Cn的鄰點可區(qū)別全染色，得到了它們的鄰點可區(qū)別全色數(shù).定義1：[1]設(shè)圖G是階至少為2的連通圖，k是正整數(shù)，f是 V（G）∪E（G）到{1，2，3，…
汕頭大學(xué)學(xué)報（自然科學(xué)版） 2022年2期2022-05-24
- 兩類正則圖的鄰點全和可區(qū)別全染色
意點的關(guān)聯(lián)邊與其鄰點所染顏色相加，定義了圖的鄰點被擴展和可區(qū)別全染色，且得到了一些特殊圖的鄰點被拓展和可區(qū)別全色數(shù)．文獻[10]研究了仙人掌圖的鄰點被拓展和可區(qū)別全染色．不僅如此，文獻[9]又在鄰點被擴展和可區(qū)別全染色的基礎(chǔ)上考慮加上點本身的顏色，介紹了下述關(guān)于圖的一類新染色——鄰點全和可區(qū)別全染色：其中N(x)={y∈V(G)|xy∈E(G)}對任意的邊uv∈E(G)，如果有φ(u)≠φ(v)成立，則稱f是圖G的一個鄰點全和可區(qū)別(簡記NFSD)k-全染
西南大學(xué)學(xué)報（自然科學(xué)版） 2022年4期2022-04-15
- 稀疏圖的(3,4)-染色
G)，若v有一個鄰點u的度為d，則稱u是v的d-鄰點.對于5 ≤k≤7,如果一個k-度點和k-1個2-度點相鄰，則稱它是壞-點.輕-點是2-度點或壞點.設(shè)G是定理的一個反例，使得|V(G)|最小.顯然，G連通且δ(G)≥2.令i∈{3,4}且c是G或G的子圖的一個染色.若c(v)=i且v有i個鄰點染顏色i，則稱v是i-飽和的.根據(jù)定義，一個i-飽和點至少有i個鄰點.用顏色3和4給G的某個子圖染色，使得染顏色i的所有頂點的導(dǎo)出子圖的最大度至多是i(i∈{3,
閩南師范大學(xué)學(xué)報(自然科學(xué)版) 2022年4期2022-04-07
- 路與幾類圖的Cartesian 積的鄰點擴展和可區(qū)別全染色
(y)，則稱f是鄰點擴展和可區(qū)別的(簡記為NESD).使得圖G存在NESDk-全染色的k的最小值被稱為圖G的鄰點擴展和可區(qū)別全色數(shù)，簡記為egndi∑(G).Kalkowski 等人[1]引入并研究了圖的鄰和可區(qū)別一般邊染色.Przybylo 和Wo′znizk[2]進一步提出鄰和可區(qū)別一般全染色的概念，該問題的相關(guān)研究見文獻[3-6].Flandrin 等人[7]在此基礎(chǔ)上提出鄰點擴展和可區(qū)別全染色，并對一些特殊圖類：路、圈、完全圖、樹等進行了研究.同時
工程數(shù)學(xué)學(xué)報 2021年5期2021-11-26
- 邊賦權(quán)簡單圖最長圈問題研究
上取1個va的相鄰點記為va′，用路徑vavbva′取代路徑vava′，得到1個新的圈，記為L′，圖形可參看圖3。圖3 va在最長圈L的示意圖根據(jù)假設(shè)有eaa′≥eab+eba′，但是實際上對于路徑vava′vb，有ea′a+eab≥2eab+eba′>2eab≥eab+ebc(3)這與路徑vavbvc是最長P3矛盾，此假設(shè)不成立，所以va?L。其次，假設(shè)L經(jīng)過vc點，在最長圈L上任取一個vc的相鄰點記為vc′，圖形見圖4。圖4 vc在最長圈L的示意圖對于
重慶理工大學(xué)學(xué)報(自然科學(xué)) 2021年9期2021-10-19
- 圍長為5的3-正則有向圖的不交圈
稱v是u的一個出鄰點，記u的所有出鄰點為ND+（u），u的出度是|ND+（u）|，記為dD+（u），即dD+（u）=|ND+（u）|，D的最小出度min{dD+（u）|u∈V}。類似地，稱u是v的一個入鄰點，記v的所有入鄰點為ND-（v），v的入度是|ND-（v）|，記為dD-（v），即dD-（v）=|ND-（v）|，D的最小入度為min{dD-（v）|v∈V}。如果U？哿V，那么由U生成的D的子有向圖記為D[U]。令D=（V，A）是一個有向圖?；。╱，v
赤峰學(xué)院學(xué)報·自然科學(xué)版 2021年4期2021-06-24
- 關(guān)于路的k-方圖的鄰點可區(qū)別-邊全染色和第一類弱全染色
別邊染色[1]、鄰點可區(qū)別邊染色[2-6]、鄰點可區(qū)別全染色[5]等都是十分困難的問題。在此基礎(chǔ)上，張忠輔等人提出了鄰點可區(qū)別-邊全染色[6]和第一類弱全染色的概念，并得到一些重要的結(jié)論。本文給出了路的k-方圖的鄰點可區(qū)別-邊全染色數(shù)和第一類弱全染色數(shù)。定義1[3]圖G(V，E)的一個正常全染色f:V∪E→{1,2,…,k}，如果滿足：1)對任意的uv∈E有f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv)2)對任意的uv,vw∈E有f(uv)
安陽師范學(xué)院學(xué)報 2021年2期2021-04-21
- 路的強積的鄰點可區(qū)別邊染色
,k為正整數(shù).由鄰點可區(qū)別邊染色概念,容易得到以下引理.引理1.1 若階至少為3的簡單圖G中存在相鄰的最大度點,則χ＇α(G)≥Δ(G)+1.zhang等在文獻[1]中提出了鄰點可區(qū)別邊染色概念,并研究了一些基本簡單圖，如路、圈、完全圖、樹等的鄰點可區(qū)別邊染色,得到了相應(yīng)的鄰點可區(qū)別邊色數(shù).Balister在文獻[2]中證明了最大度為3的圖的鄰點可區(qū)別邊色數(shù)不超過5,二部圖的鄰點可區(qū)別邊色數(shù)不超過其最大度加2,并證明這些上界是可達的.Hatami在文獻[3
西北民族大學(xué)學(xué)報（自然科學(xué)版） 2020年4期2020-12-21
- 不含相交3圈和相鄰4-圈的平面圖是(2, 2, 0)-可染的
一個d(u)-鄰點. 對任意的一個面f∈F,f的度數(shù)記作d(f). 稱f分別為k-面、k--面和k+-面， 如果d(f)=k,d(f)≤k和d(f)≥k. 稱f為一個(d(v1),d(v2), …,d(vk))-面， 如果f上的點v1,v2, …,vk是按某一時針方向連續(xù)出現(xiàn)的. 如果一個點或一條邊與一個三角形相關(guān)聯(lián)， 則稱這個點或這條邊是三角的. 稱點v是d(u)-鄰點m-面的， 如果v有一個鄰點u, 且v和鄰點u與一個m-面相關(guān)聯(lián). 稱點v是k-三角
洛陽師范學(xué)院學(xué)報 2020年11期2020-12-11
- 梯圖的鄰點可區(qū)別均勻I-全染色
等[3]提出圖的鄰點可區(qū)別I-全染色概念，王繼順等[4]提出了鄰點可區(qū)別I-均勻全染色的概念，由于其都是NP完全問題，受到圖論學(xué)者的普遍關(guān)注，楊隨義等[5]研究了冠圖的鄰點可區(qū)別I-全染色，王繼順研究了蛛網(wǎng)圖、漁網(wǎng)圖[6]以及聯(lián)圖Pm∨Fn和Pm∨Wn[7]的鄰點可區(qū)別I-全染色， 劉秀麗[8]研究了某些Mycielski圖的鄰點可區(qū)別I-全染色， 王笑妍等[9]研究了風車圖、 齒輪圖等圖的均勻鄰點可區(qū)別I-全染色， 給出了這些圖的鄰點可區(qū)別I-全色數(shù)或鄰
中北大學(xué)學(xué)報(自然科學(xué)版) 2020年5期2020-09-10
- 圖在約束條件下的鄰點可區(qū)別全染色
化, 定義了圖的鄰點可區(qū)別全染色概念, 同時給出了鄰點可區(qū)別全染色猜想: 任意圖的鄰點可區(qū)別全色數(shù)不超過Δ+3.目前，這兩個猜想均未被解決,也沒有發(fā)現(xiàn)這些猜想的反例. 為了更深入地研究圖的可區(qū)別染色問題, 本文提出了(3)-鄰點可區(qū)別全染色((3)-AVDTC) 概念,這個概念極大豐富了文獻[1-6] 中的研究內(nèi)容, 考慮的問題較以前更為全面, 為圖染色在其他領(lǐng)域中的應(yīng)用奠定了理論基礎(chǔ). 在介紹主要工作之前, 先介紹與本文相關(guān)的一些概念.文中論及的圖均為無
廣州大學(xué)學(xué)報（自然科學(xué)版） 2020年1期2020-08-04
- 若干圖的鄰點可區(qū)別的I-全染色和鄰點可區(qū)別的I-均勻全染色
同. 圖G的一個鄰點可區(qū)別的I-全染色是指:在圖G的I-全染色的基礎(chǔ)上，還滿足任意兩個相鄰頂點的色集合不同,即C(u)≠C(v),其中,C(u)={f(u)|u∈V(G)}∪{f(uv)|uv∈E(G),v∈V(G)}.而圖的鄰點可區(qū)別的I-全染色中所用顏色的最少數(shù)量稱為圖G的鄰點可區(qū)別I-全色數(shù). Zhang等[1]于2009年提出了圖的鄰點可區(qū)別I-全染色概念, 拓展了圖染色理論的應(yīng)用領(lǐng)域. 之后, 一些學(xué)者對一些特殊圖的鄰點可區(qū)別I-全染色和點可區(qū)別
廣州大學(xué)學(xué)報（自然科學(xué)版） 2020年1期2020-08-03
- T-型六角系統(tǒng)的鄰點可區(qū)別I-全色數(shù)
[1]提出了圖的鄰點可區(qū)別全染色的概念，并給出了圈、完全圖、完全二部圖等一些特殊圖類的鄰點可區(qū)別全色數(shù)，并猜測圖的鄰點可區(qū)別全色數(shù)Δ+2.此后，國內(nèi)外學(xué)者針對這一猜想展開了研究.[2，3]為了推動鄰點可區(qū)別全色數(shù)猜想的研究，張忠輔等[4]在鄰點可區(qū)別全染色的基礎(chǔ)上，提出了鄰點可區(qū)別I-全染色的概念.隨后王繼順[4,5]研究了蛛網(wǎng)圖、漁網(wǎng)圖以及聯(lián)圖Pm∨Fn及Pm∨Wn[6]的鄰點可區(qū)別I-全染色.張婷、趙慧霞等[7]給出了圖C5∨Wn的鄰點可區(qū)別I-全色數(shù)
天水師范學(xué)院學(xué)報 2020年5期2020-06-05
- 冠圖PnoCm的兩種度結(jié)合重構(gòu)數(shù)
圖，故新點v'的鄰點必落在路點主子圖的每個連通分支中。斷言：新點v'與路點主子圖G-uk中的圈分支Cm中的每個點均相鄰。(反證法)假設(shè)圈分支Cm中至少存在1個點與v'不相鄰，則當d(v')=m+1時；圖H中至少存在1個2-度點且v'至少有2個鄰點落在另一連通分支的路點或圈點中，當d(v')=m+2時，圖H中至少存在1個2-度點且v'至少有3個鄰點分別落在另兩個連通分支的路點或圈點中，故從圖H中刪除一個3-度點至多有n-2個割邊，但已知的圈主子圖中存在n-1
上饒師范學(xué)院學(xué)報 2020年3期2020-06-05
- 基于改進K均值聚類算法的燃氣泄露檢測研究
出了基于數(shù)據(jù)點的鄰點數(shù)目來選取初始聚類中心，并采用信息熵方法來確定聚類類別數(shù)目。實驗結(jié)果表明，本文提出的方法較好了解決了原始K均值方法的問題，從而能準確地給出泄露檢測結(jié)果。關(guān)鍵詞： K均值;鄰點;信息熵;泄露檢測中圖分類號： TH865 ? ?文獻標識碼： A ? ?DOI：10.3969/j.issn.1003-6970.2019.05.016本文著錄格式：李詠豪. 基于改進K均值聚類算法的燃氣泄露檢測研究[J]. 軟件，2019，40（5）：8689【
軟件 2019年5期2019-10-08
- 最大度為6的圖G的鄰點可區(qū)別邊色數(shù)的一個上界
正常邊著色φ稱為鄰點可區(qū)別邊著色,如果G的任何相鄰頂點u和v,滿足cφ(u)(v).G的鄰點可區(qū)別邊色數(shù)是使得G有一個k-鄰點可區(qū)別邊著色的最少顏色數(shù)k.在2002年,文獻[1]首先討論了鄰點可區(qū)別邊著色問題,并提出了以下猜想.猜想設(shè)圖G為頂點數(shù)至少為3的連通圖且5,則.對于一般圖G,文獻[2]給出了若?(G)>1020,則.文獻[3]給出了.文獻[4]給出了.文獻[5]給出了若?(G)≤3,則.文獻[6]給出了若?(G)≤5且,則.文獻[7]給出了若?(
數(shù)學(xué)雜志 2019年1期2019-02-18
- 輪，扇，星和雙星的鄰點擴展和可區(qū)別全染色
]在此基礎(chǔ)上提出鄰點擴展和可區(qū)別全染色，且得出了一些特殊圖的鄰點擴展和可區(qū)別全染色，提出了一個猜想.在本文中我們對輪，扇，星和雙星的鄰點擴展和可區(qū)別全染色進行研究與討論.圖G的一個全k-染色是指它的全體頂點及邊分配的色集合為{1，2，…，k}.使得圖G存在NESD全k-染色中k的最小值被稱為圖G的鄰點擴展和可區(qū)別全色數(shù)，簡記為 egndi∑（G）.文獻[5]中給出輪，扇，星和雙星的概念，對n＋1階輪Wn，設(shè)其頂點集合為V（Wn），其邊集合為{vnv1}.將
汕頭大學(xué)學(xué)報（自然科學(xué)版） 2018年4期2018-12-19
- 若干Mycielski圖鄰點可區(qū)別Ⅰ-均勻全染色
區(qū)別Ⅰ-全染色和鄰點可區(qū)別Ⅰ-全染色.文獻［9］給出了路、圈、扇、輪、完全圖、完全二部圖的鄰點可區(qū)別Ⅰ-均勻全色數(shù)，提出鄰點可區(qū)別Ⅰ－均勻全色數(shù)最大不超過2的猜想；文獻［10］研究了幾類圖的均勻鄰點可區(qū)別Ⅰ-全染色.本文根據(jù)圖M（Pn）、M（Cn）和 M（Sn）的構(gòu)造特征，利用函數(shù)構(gòu)造法，研究并確立它們鄰點可區(qū)別Ⅰ-均勻全色數(shù)，并驗證其滿足猜想.1 相關(guān)定義和引理定義1［11］對于階數(shù)不小于2的連通圖G（V，E），設(shè)f是從V（G）∪E（G）到｛1，2，…，
大連理工大學(xué)學(xué)報 2018年5期2018-09-22
- 圖的鄰點強可區(qū)別V-全色數(shù)的一個上界
通，馮苗苗?圖的鄰點強可區(qū)別V-全色數(shù)的一個上界*蔡學(xué)鵬，任佰通，馮苗苗（新疆農(nóng)業(yè)大學(xué)數(shù)理學(xué)院，新疆，烏魯木齊830052）應(yīng)用概率論中的Lovasz一般局部引理得出了圖的鄰點強可區(qū)別V-全色數(shù)的上界，證明了對階數(shù)不小于3且不含孤立邊的簡單圖的鄰點強可區(qū)別V-全色數(shù)不超過49△，△≥5。Lovasz一般局部引理；鄰點強可區(qū)別全染色；鄰點強可區(qū)別V-全染色0 引言隨著計算機的飛速發(fā)展，信息化和數(shù)字化技術(shù)的不斷進步，許多實際問題的數(shù)學(xué)模型使離散型結(jié)構(gòu)上的數(shù)字化
井岡山大學(xué)學(xué)報(自然科學(xué)版) 2018年3期2018-08-08
- 三類K重Mycielski圖的鄰點強可區(qū)別E-全染色
振現(xiàn)象提出了圖的鄰點可區(qū)別全染色[3]；2007年，張忠輔，程輝等人提出了圖的鄰點強可區(qū)別全染色[4]，文獻[5]是鄰點強可區(qū)別E-全染色的一些結(jié)果.本文在文獻[5]的基礎(chǔ)上得到了路圖，圈圖和星圖的廣義Mycielski圖的鄰點強可區(qū)別區(qū)別E-全染色，下面給出相關(guān)的定義：2 基本概念定義1[4,5]設(shè)圖G是階數(shù)至少為2的連通圖， 映射f:V(G)∪E(G)→{1,2,…,k},其中k為正整數(shù)，C(u)={f(u)}∪{f(v)}∪{f(uv)|uv∈E(G
安陽師范學(xué)院學(xué)報 2018年2期2018-05-25
- 關(guān)于廣義θ—圖的鄰點可區(qū)別染色的簡單證明
出了廣義θ-圖的鄰點可區(qū)別全染色和鄰點可區(qū)別邊染色， 但方法太過繁瑣. 本文結(jié)合P.N. Balister方法從結(jié)構(gòu)上更為簡潔的證明廣義θ-圖的鄰點可區(qū)別染色的相關(guān)猜想.關(guān)鍵詞 圖， θ-圖； 鄰點可區(qū)別全染色；鄰點可區(qū)別邊染色中圖分類號 O157.5 文獻標識碼 AAbstract In the Journal of Quantitative Economics and so on， the general method is used to give
經(jīng)濟數(shù)學(xué) 2017年4期2018-01-18
- 兩類k重Mycielski圖的鄰點強可區(qū)別E-全染色
ielski圖的鄰點強可區(qū)別E-全染色李雨虹1, 強會英1, 王洪申2(1.蘭州交通大學(xué) 數(shù)理與軟件工程學(xué)院, 甘肅 蘭州 730070;2.蘭州理工大學(xué) 機電工程學(xué)院，甘肅 蘭州 730050)應(yīng)用反證法和構(gòu)造染色函數(shù)法研究了圖Mk(Fn)和Mk(Wn)的鄰點強可區(qū)別E-全染色,并得出了其鄰點強可區(qū)別E-全色數(shù).鄰點強可區(qū)別全染色;k重Mycielski圖; 鄰點強可區(qū)別E-全染色0 引言圖論在網(wǎng)絡(luò)設(shè)計、信息科學(xué)、密碼學(xué)、DNA的基因普的確定和計數(shù)等領(lǐng)域
淮陰師范學(xué)院學(xué)報（自然科學(xué)版） 2017年3期2017-11-02
- Relation between Cartesian product andadjacent vertex distinguishing coloring
色;正常全染色;鄰點可區(qū)別邊染色;鄰點可區(qū)別全染色O 157.5：A：1008-9497(2017)05-520-06date：Dec.26, 2016.Supported by the National Natural Science Foundation of China (61662066), Gansu Business Development Research Center Project of Lanzhou University of Fin
浙江大學(xué)學(xué)報（理學(xué)版） 2017年5期2017-10-10
- 平面圖的非正常染色*
頂點至多有di個鄰點染有同樣的色(i=1,2,…,k),則稱G是非正常(d1,d2,…,dk)-可染的,簡稱為(d1,d2,…,dk)-可染的.運用這一術(shù)語,四色定理可改述為“每個平面圖是(0,0,0,0)-可染的”,Steinberg猜想可改述為“每個既沒有4-圈又沒有5-圈的平面圖是(0,0,0)-可染的”.圖的非正常染色已得到廣泛研究,并已得到許多有趣的結(jié)果.例如:每個平面圖是(2,2,2)-可染的[7];每個既不含5-圈又不含相鄰三角形的平面圖是(
浙江師范大學(xué)學(xué)報（自然科學(xué)版） 2017年3期2017-09-08
- k-樹及其鄰點可區(qū)別全染色
00)k-樹及其鄰點可區(qū)別全染色張 琛，李紅霞(隴東學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院，甘肅慶陽745000)G是一個簡單圖，G的一個全染色f是指使相鄰頂點和相鄰邊著不同顏色且每條關(guān)聯(lián)邊與它的頂點著以不同顏色的全染色。設(shè)f為圖G一個全染色，對任意x∈V(G)，用C(x)表示在f下頂點的顏色以及與x關(guān)聯(lián)的邊的顏色所構(gòu)成的集合。若任意uv∈E(G)，u≠v，有C(u)≠C(v)，則稱f是圖G的鄰點可區(qū)別的全染色，該問題的主要目的是確定圖G的鄰點可區(qū)別全色數(shù)。基于樹的基本結(jié)構(gòu)，
隴東學(xué)院學(xué)報 2017年1期2017-03-02
- 圖和的Mycielski圖的鄰點可區(qū)別I-全染色
ielski圖的鄰點可區(qū)別I-全染色，并得到了其鄰點可區(qū)別I-全色數(shù)，進一步驗證了圖的鄰點可區(qū)別I-全染色猜想．k方圖；Mycielski圖；鄰點可區(qū)別I-全染色；鄰點可區(qū)別I-全色數(shù)Noga Alon在2002年數(shù)學(xué)國際大會上作了“離散數(shù)學(xué)方法與挑戰(zhàn)”的大會報告后，圖的染色成為一個很活躍、很新穎的研究領(lǐng)域．染色理論[1]在物理、化學(xué)、新型計算機設(shè)計、計算機圖像處理、網(wǎng)絡(luò)理論、社會科學(xué)等方面有著廣泛應(yīng)用．為此，許多研究者提出了一系列染色．1993年，Bur
溫州大學(xué)學(xué)報（自然科學(xué)版） 2017年1期2017-03-01
- Mycielski圖的一般鄰點可區(qū)別全色數(shù)
lski圖的一般鄰點可區(qū)別全色數(shù)王繼順(連云港師范高等?？茖W(xué)校 數(shù)學(xué)與信息工程學(xué)院，江蘇 連云港 222006)Mycielski圖； 一般鄰點可區(qū)別全染色； 一般鄰點可區(qū)別全色數(shù)由信息科學(xué)中的電信通訊站的頻率分配問題、計算機科學(xué)中的網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計區(qū)分問題所引出的點可區(qū)別邊染色[1-3]，鄰點可區(qū)別邊染色[4-5]，鄰點可區(qū)別全染色[6]等具有一定的理論價值和實際意義，逐漸成為圖論工作者研究的重要課題[7-10]. 為拓展圖染色理論的應(yīng)用領(lǐng)域，文獻[11]進
海南大學(xué)學(xué)報（自然科學(xué)版） 2016年4期2017-01-13
- 若干路的冠圖的鄰點可區(qū)別I-全染色
?若干路的冠圖的鄰點可區(qū)別I-全染色劉秀麗(菏澤學(xué)院 數(shù)學(xué)系，山東 菏澤 274015)全染色； 鄰點可區(qū)別全染色； 鄰點可區(qū)別I-全染色； 鄰點可區(qū)別I-全色數(shù)； 冠圖0 引 言圖的染色問題是圖論的主要研究內(nèi)容之一，全染色問題特別是鄰點可區(qū)別全染色又是染色問題中的難點. 2004年，張忠輔等[1]提出了鄰點可區(qū)別全染色的概念，這個染色問題已經(jīng)被廣泛研究[2-3]. 在鄰點可區(qū)別全染色概念的基礎(chǔ)上，又提出了圖的鄰點可區(qū)別I-全染色[4]的概念. 近來，一些
中北大學(xué)學(xué)報(自然科學(xué)版) 2016年5期2016-12-22
- 兩類特殊圖的鄰點強可區(qū)別E-全染色
0）兩類特殊圖的鄰點強可區(qū)別E-全染色顧忠棟，強會英*，魏邦魁（蘭州交通大學(xué) 數(shù)理與軟件工程學(xué)院，甘肅 蘭州730070）對簡單圖G（V，E），存在一個正整數(shù)k，使得映射f：V（G）∪E（G）→｛1，2，…，k｝，如果?uv∈E（G），有f（u）≠f（v），f（u）≠f（uv）且C（u）≠C（v），其中C（u）=｛f（u）｝∪｛f（uv），f（v）|uv∈E（G），v∈V（G）｝，則稱f是圖G的鄰點強可區(qū)別E-全染色，且稱最小的數(shù)k為圖G的鄰點強可區(qū)別E-
蘇州科技大學(xué)學(xué)報(自然科學(xué)版) 2016年3期2016-09-20
- 一類特殊圖的兩種染色
圖的鄰強邊染色和鄰點可區(qū)別的全染色，通過構(gòu)造具體染色得到了該類圖的鄰強邊色數(shù)和鄰點可區(qū)別的全色數(shù)。窮舉法；鄰強邊染色；鄰點可區(qū)別的全染色圖的染色是圖論的主要研究內(nèi)容之一，很多人對其進行了研究，文獻［1］給出了圖的鄰強邊染色的概念和一些特殊圖的具體染色，文獻［2-3］通過構(gòu)造具體染色得到了一些特殊圖的鄰強邊染色數(shù)，文獻［4］給出了鄰點可區(qū)別的全染色的概念和若干特殊圖的染色，文獻［5-6］給出了若干特殊圖的鄰點可區(qū)別的全色數(shù)。本文將研究一類特殊圖的鄰強邊染色和
商洛學(xué)院學(xué)報 2016年4期2016-08-13
- 關(guān)于一類三倍圖的鄰點可區(qū)別E-全染色
關(guān)于一類三倍圖的鄰點可區(qū)別E-全染色魏邦魁，強會英，顧忠棟（蘭州交通大學(xué) 數(shù)學(xué)院，甘肅 蘭州 730070）運用分析法和窮舉法，研究了路，圈，星，扇，輪的三倍圖的鄰點可區(qū)別E-全染色，并且得到了他們的鄰點可區(qū)別E-全色數(shù)。三倍圖；鄰點可區(qū)別E-全染色；鄰點可區(qū)別E-全色數(shù)1 引言圖的染色是圖論的重要研究之一在近年來許多的圖論理論研究者們提出了一系列的新的染色問題，如：點可區(qū)別全染色，鄰點可區(qū)別全染色，以及鄰點可區(qū)別E-全染色，本文主要研究了三倍圖（路，圈，
唐山師范學(xué)院學(xué)報 2016年2期2016-02-07
- 路、扇及星的Mycielski圖的鄰點可區(qū)別I-全染色
全染色問題特別是鄰點可區(qū)別全染色又是染色問題中的難點.2004年，張忠輔等［2］提出了鄰點可區(qū)別全染色的概念，這個染色問題已經(jīng)被廣泛研究［3-5］.在鄰點可區(qū)別全染色概念的基礎(chǔ)上，又提出了圖的鄰點可區(qū)別I-全染色的概念.近年來，一些學(xué)者對一些特殊圖類的鄰點可區(qū)別I-全染色進行了研究［6-11］，本文討論了M（Pn），M（Fn）和M（Sn）圖的鄰點可區(qū)別I-全染色，根據(jù)M（Pn），M（Fn）和M（Sn）圖的特征，給出了一種具體的染色方案，得到了它們的鄰點可區(qū)
中北大學(xué)學(xué)報(自然科學(xué)版) 2015年4期2015-12-02
- On Chromatic Number and Adjacent Vertex-dis?tinguishing E-total Chromatic Number of Graphs
）：圖1 圖G的鄰點可區(qū)別E-全染色Fig.1k-AVDETC ofGIt is not difficult to verity thatfis ak-AVDETC ofG.3 RemarksThe Cartesian product of two graphsG1andG2is the graphG1×G2whose vertex set isV（G1）×V（G2）and whose edge set is the set of all pairs（u，
海南師范大學(xué)學(xué)報（自然科學(xué)版） 2015年2期2015-09-03
- 關(guān)于一類圖的鄰點可區(qū)別全染色*
8)關(guān)于一類圖的鄰點可區(qū)別全染色*胡鳳鳳1，劉家保2(1．安徽大學(xué)數(shù)學(xué)科學(xué)學(xué)院，合肥 230601;2．安徽新華學(xué)院公共課教學(xué)部，合肥 230088)圖G的一個正常全染色f稱為是鄰點可區(qū)別的，如果G中任何相鄰點及其關(guān)聯(lián)邊的顏色集合不同;對一個圖G進行鄰點可區(qū)別的正常全染色所用最少顏色數(shù)稱為G的鄰點可區(qū)別全色數(shù)，記為 χat(G);給出了一類特殊圖類的鄰點可區(qū)別全色數(shù)．正常全染色;鄰點可區(qū)別全染色;鄰點可區(qū)別全色數(shù)具有重要實際意義和理論意義的圖的染色問題，是
重慶工商大學(xué)學(xué)報（自然科學(xué)版） 2015年2期2015-05-25
- 關(guān)于邊柒色臨界圖的獨立數(shù)
表示與x相鄰接的鄰點.1965年，Vizing證明了：最大度為Δ的圖G，其邊色數(shù)χ′（G）要么是Δ，要么是Δ+1.如果χ′（G）=Δ，則稱圖G是第一類的；如果χ′（G）=Δ+1.則稱圖G是第二類的.如果圖G是連通的和第二類的，且對每條邊χ′（G-e）＜χ′（G），則稱G是臨界圖.1968年，Vizing提出了如下臨界圖獨立數(shù)的猜想［1］：若G是n階Δ臨界圖，則有α（G）≤.2000年，Birnkmann證明了：（2）如果G是一個n階臨界圖，則對較小的最大度
華東師范大學(xué)學(xué)報（自然科學(xué)版） 2015年1期2015-03-18
- 特殊圖的廣義字典積的鄰點可區(qū)別全染色
圖的廣義字典積的鄰點可區(qū)別全染色趙曉翠，田雙亮，何雪，焉秋瑤（西北民族大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院，甘肅蘭州730030）設(shè)G是具有頂點集V（G）＝{t0，…，tn-1}（n≥2）的圖，hn=（Hi）i∈{0,1，…，n-1}是不相交圖的序列，其中Hi的頂點集為V（Hi）={（ti，y1)，…，（ti，yx)}，x≥1。稱G[hn]為G與hn=（Hi）i∈{0,1，…，n-1}的廣義字典積，其中G[hn]的頂點集為，且兩個頂點（ti，yp)與（tj，yq)相鄰
蘇州科技大學(xué)學(xué)報(自然科學(xué)版) 2015年1期2015-01-10
- 齒輪圖的鄰點強可區(qū)別的全染色
，商洛)齒輪圖的鄰點強可區(qū)別的全染色張東翰，李 超(商洛學(xué)院數(shù)學(xué)與計算機應(yīng)用學(xué)院，726000，陜西，商洛)齒輪圖；鄰點強可區(qū)別的全染色；鄰點強可區(qū)別的全色數(shù)0 引言1 預(yù)備知識定義1[7]：設(shè)G(V,E)是階數(shù)不小于3的簡單連通圖，k是自然數(shù)，f是從V(G)∪E(G)到{1,2…k}的映射，如果滿足：1)對任意的邊uv∈E(G),f(u)≠f(v),f(u)≠f(uv)≠f(v)；2)對任意的兩相鄰的邊uv,uw∈E(G)(v≠w),f(uv)≠f(uw
江西科學(xué) 2014年4期2014-09-08
- 復(fù)合交叉圈的鄰點可區(qū)別全色數(shù)
[1-4].圖的鄰點可區(qū)別全染色的概念第一次被張忠輔等[5]提出,并提出了以下的鄰點可區(qū)別全染色猜想:猜想1[5]對于階數(shù)不小于 2的簡單連通圖G,有然而, 諸多文獻的結(jié)論表明, 解決上述猜想較困難. 近些年來,對此猜想的研究成果不斷報道[6-10],Wang等[7]對平面圖驗證了鄰點可區(qū)別全染色猜想, 取得了較好的結(jié)論. 令平面圖G的最小圈長為g(G), 他們證明了: 當g(G)≥6和Δ(G)=4時,當g(G)≥8和Δ(G)=3時,5. 然而,對于最小圈
華南師范大學(xué)學(xué)報（自然科學(xué)版） 2014年1期2014-08-28
- 路和圈冪圖的鄰點可區(qū)別E-全染色
染色［2－3］，鄰點可區(qū)別的邊染色［4－5］，點可區(qū)別的全染色［6］，鄰點可區(qū)別的全染色［7］等;2008 年張忠輔［8］等人又提出了圖的鄰點可區(qū)別E-全染色的概念，李沐春、王治文、王繼順［9－12］等研究了一些圖的鄰點可區(qū)別E-全染色. 確定圖的鄰點可區(qū)別E-全色數(shù)同樣是NP-難問題.定義1［8］對簡單連通圖G(V，E)和正整數(shù)k，f 是T(G)到［k］={1，2，…，k}的一個映射，如果f 滿足則稱f 為一個圖G 的鄰點可區(qū)別E-全染色，簡記為G 的k
海南大學(xué)學(xué)報（自然科學(xué)版） 2014年3期2014-07-10
- 圖Dn,4的鄰點強可區(qū)別的全染色
0）圖Dn,4的鄰點強可區(qū)別的全染色張東翰（商洛學(xué)院 數(shù)學(xué)與計算機應(yīng)用學(xué)院，陜西商洛726000）通過分析圖Dn,4的結(jié)構(gòu)，利用窮舉法和組合分析法討論了圖Dn,4的鄰點強可區(qū)別的全染色，通過構(gòu)造具體染色得到了圖Dn,4的鄰點強可區(qū)別的全色數(shù)。從而證明了圖Dn,4的鄰點強可區(qū)別的全色數(shù)是存在的。窮舉法；組合分析法；色數(shù)張忠輔教授提出了圖的鄰點強可區(qū)別的全染色的概念[1]，隨后很多學(xué)者對其進行了研究，迄今，劉永平等[2]給出了Pn×Pm的鄰點強可區(qū)別的全染色，
商洛學(xué)院學(xué)報 2014年6期2014-04-11
- 一類二部圖生成的廣義格子圖的鄰點可區(qū)別邊染色
線通信網(wǎng)等引出的鄰點可區(qū)別邊染色問題，得到國內(nèi)外圖論研究者的關(guān)注.近些年來，雖然許多學(xué)者在這一領(lǐng)域已經(jīng)取得了很多成果［1－8］，但這方面的研究工作尚屬開始，許多猜想的解決處于特殊圖的驗證階段.本文定義了一類2維廣義格子圖H2（G，n，m；k1，k2），且通過從圖的結(jié)構(gòu)出發(fā)，利用構(gòu)造染色的方法，得到了圖H2（Kp，p，n，m；p，p）的鄰點可區(qū)別邊色數(shù).從而驗證了鄰點可區(qū)別邊色數(shù)猜想.定義1［1］設(shè)G（V，E）是階數(shù)至少為3的簡單連通圖，k－是正整數(shù).若G（
東北師大學(xué)報（自然科學(xué)版） 2014年3期2014-03-02
- K2n-1×K2n+1'的鄰點可區(qū)別全染色①
［1］提出了圖的鄰點可區(qū)別全染色這一新概念，得到了一些有價值的成果，并根據(jù)這些結(jié)果提出了一個猜想:對于階數(shù)不小于2 的簡單連通圖，其鄰點可區(qū)別全色數(shù)不超過最大度加3.要完全證明這一結(jié)論較為困難，但目前已有的結(jié)果中，該猜想均成立.本文中所討論的相鄰奇數(shù)階完全圖的直積圖的鄰點可區(qū)別全色數(shù)也不超過這一上界.1 定義及引理本文所考慮的圖均為連通、有限、無向的簡單圖.Δ(G)，d(v)分別表示圖G 的最大度和圖G 中頂點v 的度.其它術(shù)語及符號參［2］.定義1 對圖
佳木斯大學(xué)學(xué)報（自然科學(xué)版） 2013年3期2013-02-02
- K4-minor-free圖的鄰點可區(qū)別全染色
r-free圖的鄰點可區(qū)別全染色史小藝，張寧，萬慧敏（中國礦業(yè)大學(xué) 理學(xué)院，江蘇 徐州 221008）圖G的一個正常全染色被稱為鄰點可區(qū)別全染色，如果G中任意兩個相鄰點的色集合不同.論文確定了 k4-minor-free圖的鄰點可區(qū)別全色數(shù).全染色；鄰點可區(qū)別全染色；鄰點可區(qū)別全色數(shù)； k4-minor-free圖本文所考慮的圖均為連通、有限、無向的簡單圖. V（ G）和 E（ G）分別表示圖G的頂點集和邊集，δ（ G）和Δ （G）分別表示G中頂點的最小度
五邑大學(xué)學(xué)報（自然科學(xué)版） 2012年4期2012-10-23
- 圖Pn□Cm的鄰點可區(qū)別I-全染色
)圖Pn□Cm的鄰點可區(qū)別I-全染色楊曉亞(天水師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院,甘肅 天水 741001)通過對圖Pn□Cm的積圖的鄰點可區(qū)別全染色研究,來進一步驗證鄰點可區(qū)別全染色的猜想.應(yīng)用構(gòu)造具體染色的方法給出了圖Pn□Cm的積圖的鄰點可區(qū)別全染色.得到了圖Pn□Cm的積圖的鄰點可區(qū)別全染色的色數(shù).I-全染色;鄰點可區(qū)別I-全染色;鄰點可區(qū)別I-全色數(shù)1 引言圖的染色是圖論的重要研究內(nèi)容之一,由計算機科學(xué)和信息科學(xué)等所產(chǎn)生的點可區(qū)別邊染色[1-9],鄰點可區(qū)
- 關(guān)于圖的鄰點可區(qū)別全色數(shù)的上界研究
079)關(guān)于圖的鄰點可區(qū)別全色數(shù)的上界研究劉利群1,陳祥恩2(1.長江大學(xué)信息與數(shù)學(xué)學(xué)院,湖北 荊州 434023;2.西北師范大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院,甘肅 蘭州 730079)圖G的鄰點可區(qū)別全染色是指G存在一個正常全染色f使得任意相鄰兩點有不同的色集合.本文主要研究鄰點可區(qū)別正常全色數(shù)的上界,目前鄰點可區(qū)別全染色的一個較好的上界是?+C+20,本文用概率方法改進了這個結(jié)果,得到了鄰點可區(qū)別全色數(shù)的一個較小上界?+C+3.鄰點可區(qū)別全染色;鄰點可區(qū)別全色
- 若干冠圖的鄰點可區(qū)別E-全染色
70)若干冠圖的鄰點可區(qū)別E-全染色張 荔，文 飛，李沐春(蘭州交通大學(xué)數(shù)理與軟件工程學(xué)院，甘肅蘭州 730070)運用分析法和構(gòu)造鄰點可區(qū)別E-全染色函數(shù)法，研究了冠圖的鄰點可區(qū)別E-全染色，得到了冠圖圈與圈、圈與星、圈與扇和圈與輪的鄰點可區(qū)別E-全色數(shù)，進一步驗證了圖的鄰點可區(qū)別E-全染色猜想．冠圖；鄰點可區(qū)別E-全染色；鄰點可區(qū)別E-全色數(shù)圖的染色是圖論的重要研究內(nèi)容之一．近年來，許多圖論研究者提出了一系列染色問題，如：點可區(qū)別全染色[1]、鄰點可區(qū)
溫州大學(xué)學(xué)報（自然科學(xué)版） 2012年3期2012-01-12
- ＊ 兩類3－正則圖的鄰點可區(qū)別I－全染色
兩類3－正則圖的鄰點可區(qū)別I－全染色楊隨義，楊曉亞，唐保祥，何萬生（天水師范學(xué)院 數(shù)學(xué)與統(tǒng)計學(xué)院，甘肅 天水 741001）圖G的I－全染色是指若干種顏色對圖G的頂點和邊的一個分配，使得任意兩個相鄰的點的顏色不同，任意兩條相鄰的邊的顏色不同.在圖G的一個I－全染色下，G的任意一個點的色集合是指該點的顏色以及與該點相關(guān)聯(lián)的全體邊的顏色構(gòu)成的集合.圖G的一個I－全染色稱為是鄰點可區(qū)別的，如果任意兩個相鄰點的色集合不相等.對一個圖G進行鄰點可區(qū)別I－全染色所用的
山西大學(xué)學(xué)報（自然科學(xué)版） 2012年4期2012-01-11
- 恰有兩個主特征值的三圈圖
個頂點，如果v的鄰點中恰有2個頂點不是懸掛點，則稱v為圖G的一個柄點(knob).容易看出，(a,b)-度線性圖中的柄點的度必為2或a+b.圖G中頂點v的離徑RG(v)定義為：RG(v)=maxu∈V(G)d(v,u).設(shè)G是含圈連通圖，割邊e=uv,且滿足G-e的2個連通分支一個是樹，另一個是帶圈圖，分別記Gu,Gv,我們稱頂點u為v的外鄰點，記所有v的外鄰點的集合為O(v),v的鄰點集中不屬于O(v)中頂點的集為內(nèi)鄰點集，記為I(v).設(shè)Tv={v}∪
湖南師范大學(xué)自然科學(xué)學(xué)報 2011年4期2011-11-26
- 一類3-正則圖的關(guān)聯(lián)鄰點可區(qū)別全染色
3-正則圖的關(guān)聯(lián)鄰點可區(qū)別全染色楊隨義1,王治文2(1.天水師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院,甘肅天水741000; 2.寧夏大學(xué)數(shù)學(xué)計算機學(xué)院,寧夏銀川750021)對簡單圖G(V,E),f是從V(G)∪E(G)到{1,2,…,k}的映射,k是自然數(shù),若f滿足(1)?uv∈E(G),u≠v,f(u)≠f(v);(2)?uv,uw∈E(G),v≠w,f(uv)≠f(uw);(3)?uv∈E(G),C(u)≠C(v);其中C(u)={f(u)}∪{f(uv)|uv∈E
山西大學(xué)學(xué)報（自然科學(xué)版） 2010年3期2010-11-02
- 邊染色 9-臨界圖邊數(shù)的新下界
(x)+1個Δ度鄰點。引理 2[4]設(shè) G是Δ-臨界圖,xy∈E(G),且d(x)+d(y)=Δ +2,則有 :(1)x、y的所有鄰點 (除去 x、y)均為Δ度點;(2)與 x、y距離為 2的頂點的度至少為Δ-1;(3)當 d(x)、d(y)引理 3[4]設(shè) G是Δ-臨界圖,Δ≥5,d(x)=3,則 x至少有兩個Δ度鄰點,它的頂點中除了 x外其余的點的度都大于等于Δ-1。引理 4[5]設(shè) G是Δ-臨界圖,d(x)=4,若Δ≥6,則有:(1)若 x鄰接一個Δ
黑龍江科技大學(xué)學(xué)報 2010年5期2010-09-23
- 廣義Mycielski圖的鄰點可區(qū)別的非正常全染色
恩等人引入了圖的鄰點可區(qū)別的全染色的概念[1],許多學(xué)者對圖的鄰點可區(qū)別的全染色的理論作了大量的研究. 2005年,文獻[2]提出了圖的鄰點可區(qū)別非正常邊色數(shù)及全色數(shù)(一般鄰點可區(qū)別色指標)的概念(General neighbour-distinguishing index of a graph).另外,文中一些其他術(shù)語及符號參見文獻[3].下面給出一些相關(guān)概念:定義1[1]對階數(shù)至少為2的連通圖G(V,E),令f為從V(G)∪E(G)到{1,2,…,k}
通化師范學(xué)院學(xué)報 2010年12期2010-03-22
- 廣義Mycielski圖的鄰點可區(qū)別的非正常全染色
恩等人引入了圖的鄰點可區(qū)別的全染色的概念[1],許多學(xué)者對圖的鄰點可區(qū)別的全染色的理論作了大量的研究. 2005年,文獻[2]提出了圖的鄰點可區(qū)別非正常邊色數(shù)及全色數(shù)(一般鄰點可區(qū)別色指標)的概念(General neighbour-distinguishing index of a graph).另外,文中一些其他術(shù)語及符號參見文獻[3].下面給出一些相關(guān)概念:定義1[1]對階數(shù)至少為2的連通圖G(V,E),令f為從V(G)∪E(G)到{1,2,…,k}
通化師范學(xué)院學(xué)報 2010年12期2010-01-25