若干合成图的星全染色  

Star Total Colorings of Some Composition Graphs

作　　者：王晓琦[1] 田双亮[1] 

机构地区：[1]西北民族大学数学与计算机科学学院,兰州730030

出　　处：《武汉理工大学学报（交通科学与工程版）》2012年第5期1098-1100,共3页Journal of Wuhan University of Technology（Transportation Science & Engineering）

基　　金：国家民委科研项目资助(批准号:10XB01)

摘　　要：简单图G和H的合成图是指具有顶点集V(G)×V(H)的简单图G[H],它的顶点(u,v)和另一个顶点(u′,v′)相邻当且仅当或者uu′∈E(G),或者u=u′且vv′∈E(H).文中研究了n+1阶简单图G与m阶简单图H的合成图的星全染色,其中G为轮Wn,扇Fn,或星Sn.得到以下结果:(1)若Δ(H)=2且n≥4,m≥5,则G[H]的星全色数为(2n+1)m;(2)若χ′(H)=Δ(H)=m-1且n,m≥4,则G[H]的星全色数为2(n+1)m-1.The composition of simple graphs G and H is the simple graph G[H] with vertex set V（G） X V（H）, in which （u,~） is adjacent to （u＇ ,v＇） if and only if either uu＇ 6： E（G） or u=u＇ and vv＇ 6： E（H）. The paper focused on the star total coloring of the composition of a simple graph G with n＋1 vertices and a simple graph H with m vertices, where O is a wheel, fan, or star. And the following results are obtained： （1） if △（H）=2 and n≤4,m≥5, then the star total chromatic number of graph G[H] is （2n＋1）m; （2） if X （H）=A（H）=m-1, and n,m≥4, then the star total chromatic number of graph G[H] is 2（n＋1）m-1. Key words：composition graph; star total coloring; star total chromatic number

关 键 词：合成图 星全染色 星全色数 

分 类 号：O157.5[理学—数学]