赵永强,冯文莉,李 红,杨静梅

(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-),男,河北元氏人,副教授,博士,主要从事图论与离散几何方面的研究。