一些图运算下的k-角色分配
2010-12-26赵永强冯文莉杨静梅
赵永强,冯文莉,李 红,杨静梅
(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-),男,河北元氏人,副教授,博士,主要从事图论与离散几何方面的研究。
