本文選題：半強(qiáng)積 + 樹��； 參考：《運(yùn)籌學(xué)學(xué)報(bào)》2017年03期

【摘要】：兩個(gè)簡(jiǎn)單圖G與H的半強(qiáng)積G·H是具有頂點(diǎn)集V(G)×V(H)的簡(jiǎn)單圖,其中兩個(gè)頂點(diǎn)(u,v)與(u',v')相鄰當(dāng)且僅當(dāng)u=u'且vv'∈E(H),或uu'∈E(G)且vv'∈E(H).圖的鄰點(diǎn)可區(qū)別邊(全)染色是指相鄰點(diǎn)具有不同色集的正常邊(全)染色.統(tǒng)稱圖的鄰點(diǎn)可區(qū)別邊染色與鄰點(diǎn)可區(qū)別全染色為圖的鄰點(diǎn)可區(qū)別染色.圖G的鄰點(diǎn)可區(qū)別染色所需的最少的顏色數(shù)稱為鄰點(diǎn)可區(qū)別染色數(shù),并記為X_a~((r))(G),其中r=1,2,且X_a~((1))(G)與X_a~((2))(G)分別表示G的鄰點(diǎn)可區(qū)別的邊色數(shù)與全色數(shù).給出了兩個(gè)簡(jiǎn)單圖的半強(qiáng)積的鄰點(diǎn)可區(qū)別染色數(shù)的一個(gè)上界,并證明了該上界是可達(dá)的.然后,討論了兩個(gè)樹的不同半強(qiáng)積具有相同鄰點(diǎn)可區(qū)別染色數(shù)的充分必要條件.另外,確定了一類圖與完全圖的半強(qiáng)積的鄰點(diǎn)可區(qū)別染色數(shù)的精確值.
[Abstract]:The semi-strong product G H of two simple graphs G and H is a simple graph with vertex set V (G) 脳 V (H), where two vertices (UV) are adjacent to (UVV') if and only if uu 'and vv' 鈭，

本文編號(hào)：2052631