摘要
简单图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
出处
《武汉理工大学学报（交通科学与工程版）》
2012年第5期1098-1100,共3页
Journal of Wuhan University of Technology（Transportation Science & Engineering）
基金
国家民委科研项目资助(批准号:10XB01)
关键词
合成图
星全染色
星全色数
composition graph
star total coloring
star total chromatic number
