一些乘積圖的L(2，1)-圓標(biāo)號(hào).pdf

1、L(2,1)標(biāo)號(hào)問(wèn)題是經(jīng)典著色問(wèn)題的一個(gè)推廣，而L(2,1)圓標(biāo)號(hào)問(wèn)題對(duì)L(2,1)標(biāo)號(hào)問(wèn)題的一個(gè)變形，社k是一個(gè)正整數(shù)，f:V(G)→{0,1,2,…,k-1}是一個(gè)映射，如果成立，其中｜X｜k:=min{｜X｜,k-｜X｜},則稱f是圖G的一個(gè)k-L(2,1)-圓標(biāo)號(hào)，圖G的L(2,1)，圓標(biāo)號(hào)數(shù)，記作σ2,1(G)，定義為：
　　 給定兩個(gè)圖G和H，G和H的直積圖，記為G×H，其頂點(diǎn)集合定義為v(a×H)=V(G)×V（H

2、），邊集合定義為E（G×H）={（（x,y）,（x,y））｜xx'∈E(G)且yy'∈E（H））.給定兩個(gè)圖G和H，G和H的笛卡爾乘積圖，記為G□H，其頂點(diǎn)集合定義為V(GH)=V(G)×V(H)，邊集合定義為E（G□H）={（（x,y）,（x',y'）｜x=x'且yy'∈E（H）或者y=y'且xx'∈E(G)}.
　　 本文完全確定了路和完全圖的直積圖的L(2，1).圓標(biāo)號(hào)數(shù)，以及路和圈的笛卡爾乘積圖的L(2，1)-圓標(biāo)號(hào)數(shù).