趙永強(qiáng),馮文莉,李 紅,楊靜梅

(1.石家莊學(xué)院數(shù)學(xué)與信息科學(xué)系,河北石家莊 050035;2.東北大學(xué)秦皇島分校經(jīng)濟(jì)系,河北秦皇島 066004;3.河北科技大學(xué)理學(xué)院,河北石家莊 050018)

一些圖運(yùn)算下的k-角色分配

趙永強(qiáng)1,馮文莉1,李 紅2,楊靜梅3

(1.石家莊學(xué)院數(shù)學(xué)與信息科學(xué)系,河北石家莊 050035;2.東北大學(xué)秦皇島分校經(jīng)濟(jì)系,河北秦皇島 066004;3.河北科技大學(xué)理學(xué)院,河北石家莊 050018)

給定圖G,考慮從其頂點(diǎn)集到角色集{1,2,…,k}的一個(gè)滿射r。對任意2個(gè)具有相同角色的頂點(diǎn),如果它們鄰域所擁有的角色構(gòu)成的集合相同,則稱r為G的一個(gè)k-角色分配。對一些圖運(yùn)算下的k-角色分配進(jìn)行了研究,這些圖運(yùn)算包括聯(lián)、笛卡爾積、字典式積、弱直積,Mycielski圖。

角色分配;k-角色分配;k-角色可分配的

1 引 言

圖的角色分配概念是由EV ERETT和BORGA TTI[1]提出的,他們稱之為角色染色,公式化了源于社會網(wǎng)絡(luò)理論中的一個(gè)思想:具有相同社會角色的個(gè)體與具有相應(yīng)角色的個(gè)體有相同的關(guān)系。

則稱函數(shù)r是G的一個(gè)角色分配。如果r(V(G))={1,2,…,k},則稱r為G的k-角色分配。如果圖G有1個(gè)k-角色分配,則稱G為k-角色可分配的。

至今已有許多研究角色分配、k-角色分配及其推廣的文章,見參考文獻(xiàn)[1]—文獻(xiàn)[8]。本文研究一些圖運(yùn)算下的k-角色分配,這些圖運(yùn)算包括聯(lián)、笛卡爾積、字典式積、弱直積、Mycielski圖。文中所討論的圖均為單圖。2個(gè)有限集A和B的直積為A×B={(x,y):x∈A,y∈B}。為了方便,記A×?=?×A=?。

2 圖的聯(lián)

則容易檢查r是G的一個(gè)k-角色分配。

綜合情形1和情形2,定理得證。

定理5 任意2k個(gè)或更多個(gè)圖的聯(lián)是k-角色可分配的。

證明 把{1,2,…,k}中的每個(gè)角色分配給任意2個(gè)圖的所有頂點(diǎn),如果還有其他頂點(diǎn),就把{1,2,…,k}中的角色任意分給它們,則這些圖的聯(lián)圖的任意頂點(diǎn)的鄰域的角色集都是{1,2,…,k}。所以結(jié)論成立。

定理6 令G和H為任意2個(gè)圖。如果每個(gè)圖至少有k個(gè)頂點(diǎn),則G∨H是k-角色可分配的。

證明 由于G和H分別有至少k個(gè)頂點(diǎn),任意給G和H的頂點(diǎn)分配角色,只需讓2個(gè)圖的角色集都是{1,2,…,k}。這樣對于任意頂點(diǎn)v∈V(G∨H),NG∨H(v)的角色集均為{1,2,…,k}。所以G∨H是k-角色可分配的。

以下結(jié)果是定理6的直接推論。

推論3 令F是一個(gè)有限圖集,|F|≥2。如果對于任意G∈F,有|V(G)|≥k,則F中所有圖的聯(lián)是k-角色可分配的。

由推論3,下面結(jié)論是顯然的。

推論4 任意2個(gè)或更多個(gè)k-角色可分配圖的聯(lián)圖是k-角色可分配的。

3 圖的笛卡爾積

圖G和H的笛卡爾積是一個(gè)圖,記作G×H,其頂點(diǎn)集為V(G×H)=V(G)×V(H),邊集E(G×H)是由下面方法構(gòu)成的。

頂點(diǎn)(u,v)和(u′,v′)相鄰,當(dāng)且僅當(dāng) 1)u=u′并且vv′∈E(H);或者 2)v=v′并且uu′∈E(G)。

注意,在此筆者用(u,v)表示積圖的頂點(diǎn),而不表示從u到v的有向邊。

根據(jù)定義,筆者通過以下方法來構(gòu)造G×H:首先用H替換G的每個(gè)頂點(diǎn),如果x和y為G的2個(gè)相鄰頂點(diǎn),則連接分別替換x和y的2個(gè)H中相對應(yīng)的頂點(diǎn)。由此構(gòu)造,可得以下引理。

引理2 對任意頂點(diǎn)(u,v)∈V(G×H),有N((u,v))=({u}×N(v))∪(N(u)×{v})。

定理7 如果G是一個(gè)沒有孤立頂點(diǎn)的圖或空圖,H是一個(gè)k-角色可分配圖,則G×H是k-角色可分配的。

推論5 如果G是一個(gè)沒有孤立頂點(diǎn)的圖或者是空圖,Km是m階完全圖,則G×Km是k-角色可分配的,其中1≤k≤m。

證明 因?yàn)楫?dāng)1≤k≤m時(shí),Km是k-角色可分配的,所以由定理7立即可得結(jié)論。

4 圖的字典式積

5 圖的弱直積

圖G和H的弱直積是一個(gè)圖(見文獻(xiàn)[10]和文獻(xiàn)[11]),記作G?H,

6 Mycielski圖

進(jìn)一步的結(jié)果類似可證。

[1]EVERETT M G,BORGA TTIS.Role colouring a graph[J].Math Soc Sci,1991,21:183-188.

[2]PEKEC A,ROBERTS F S.The role assignment model nearly fitsmost social networks[J].Math Soc Sci,2001,41:275-293.

[3]ROBERTS F S.Role assignments and indifference graphs[A].Recent Trends in Mathematical Psychology[C].Mahwah:Law rence Erlbaum Associates,1998.24-28.

[4]ROBERTS F S,SHENG L.Role p rimitive indifference graphs and the role assignments on w-fan graphs[J].Congr Numerantium,1996,121:65-75.

[5]ROBERTS F S,SHENG L.Threshold role assignments[J].Congr Numerantium,1997,123:135-148.

[6]ROBERTS F S,SHENG L.Role assignments[A].Combinatorics,Grsph Theory and Algorithms[C].Kalamazoo M I:New Issues Press,1999.729-745.

[7]ROBERTS F S,SHENG L.How hard is it to determine if a graph has a 2-role assignment[J].Networks,2001,37:67-73.

[8]SHENG L.2-role assignments on triangulated graphs[J].Theoret Comput Sci,2003,304:201-214.

[9]CANOY SR,GARCES IJ L.Convex sets under some graph operations[J].Graphs and Comb,2002,18:787-793.

[10]HAGGKV IST R.On multiplicative graphs and the p roduct conjecture[J].Combinatorica,1988,8:63-74.

[11]ZHU X.Star chromatic number and p roducts of graphs[J].J Graph Theory,1992,16:557-569.

[12]CHANG G J,HUANG L,ZHU X.The circular chromatic number of Mycielski’s graphs[J].Discrete Math,1999,205:23-37.

[13]M YCIELSKIJ.Sur le coloring des graphs[J].Colloq Math,1955,3:161-162.

k-role assignments under some graph operations

ZHAO Yong-qiang1,FENGWen-li1,L IHong2,YANG Jing-mei3
(1.Department of Mathematics and Info rmation Science,Shijiazhuang University,Shijiazhuang Hebei 050035,China;2.Department of Economics,Northeast University at Qinhuangdao,Qinhuangdao Hebei 066004,China;3.College of Sciences,Hebei University of Science and Technology,Shijiazhuang Hebei 050018,China)

Given graphG,we consider a surjective functionrmapping each vertex into a role,a positive integer in{1,2,…,k}.Fo r any two verticesw ith the same role,if the setsof roles assigned to their neighbo rs are the same,then we callrak-role assignment.In this paper we study thek-role assignments under some graph operations including join,cartesian p roduct,lexicographic p roduct,categorical p roduct and Mycielski’s graphs.

role assignment;k-role assignment;k-role assignable

O157.5

A

1008-1542(2010)06-0501-07

2010-04-28;責(zé)任編輯:張 軍

趙永強(qiáng)(1970-),男,河北元氏人,副教授,博士,主要從事圖論與離散幾何方面的研究。