笛卡尔积图P_m×P_n的IC-着色  

IC-coloring of Cartesian Product P_m×P_n

作　　者：陈剑峰[1] 

机构地区：[1]湄洲湾职业技术学院基础部,福建莆田351254

出　　处：《莆田学院学报》2011年第2期13-15,共3页Journal of putian University

摘　　要：设G是一个连通图,f个将顶点集V G对应到正整数集N的函数,对G的任意子图H,我们定义fs H=Σν∈V(H)fν。如果对任意的整数k∈Σ1,fs GΣ,存在一个G的连通子图H,使得fs H=k,则称f为图G的一个IC-着色。并定义图G的IC-指数M G为使得顶点和最大时的fs G。对两条路的笛卡尔图的IC-着色进行研究,得到了它的一个下界:对任意的2≤m≤n,有M Pm×Pn≥2m-1 2n-1。Let G be a connected graph,and let f be a function mapping V G into N.We define fs H = Σν∈V（H） f ν for each subgraph H of G.The function f is called an IC-coloring of G if for each integer k in the set Σ1,fs GΣthere exists an（induced） connected subgraph H of G such that fs H =k,and the IC-index of G,M G,is the maximum value of fs G where f is an IC-coloring of G.In this paper,we prove that for 2≤m≤n,M Pm×Pn≥2m-1 2n-1.

关 键 词：IC-着色 IC-指数 路 笛卡尔积图 

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