一些圖運算下的k-角色分配

趙永強,馮文莉,李 紅,楊靜梅

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

一些圖運算下的k-角色分配

趙永強1,馮文莉1,李 紅2,楊靜梅3

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

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

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

1 引 言

圖的角色分配概念是由EV ERETT和BORGA TTI[1]提出的,他們稱之為角色染色,公式化了源于社會網絡理論中的一個思想:具有相同社會角色的個體與具有相應角色的個體有相同的關系。

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

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

2 圖的聯

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

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

定理5 任意2k個或更多個圖的聯是k-角色可分配的。

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

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

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

以下結果是定理6的直接推論。

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

由推論3,下面結論是顯然的。

推論4 任意2個或更多個k-角色可分配圖的聯圖是k-角色可分配的。

3 圖的笛卡爾積

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

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

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

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

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

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

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

證明 因為當1≤k≤m時,Km是k-角色可分配的,所以由定理7立即可得結論。

4 圖的字典式積

5 圖的弱直積

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

6 Mycielski圖

進一步的結果類似可證。

[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;責任編輯:張 軍

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