棒棒糖图的IC-着色和IC-指数.pdfVIP

第3l卷第6期 华 东 交 通 大 学 学 报 V01．31 No．6 2014年 12月 Journal of East China Jiaotong University Dec．，2014 文章编号：1005．0523(2014)06．0108．06 棒棒糖图的IC-着色和IC一指数 张楚文，王力工 (西北工业大学理学院应用数学系，陕西 西安 710072) 摘要：棒棒糖图 …是由圈c上的任一个顶点和路P 的一个1度顶点重合而得到n+m一1阶连通图。研究了棒棒糖图 的Ic一着色和Ic一指数，推出了它的IC-指数的一个上界，并借助计算机编程，证明了m分别为3，4，5时的几种棒棒糖图曰～ 的lC一着色和IC一指数。当m=3，n=1，2，…，6时，有 (曰)=5n+2；当m=4，n=1，2，…，5时，有 ． ，)=13，M ，)=21， )=26，M(B．)=34，M(B．)=40；当trt=5，n：1，2，3，4时，有M )：21，M(B，。)：31，M(B，，)=39，M(B，)=48。 ． ， 关键词：IC一着色；IC一指数；棒棒糖图 中图分类号：0157．5 文献标志码 ：A 1 引言及定义 图的IC一着色问题有着很强的实际背景，它源自数论中的邮票问题 ，近年来在无线电网络通信中有所 应用，例如程卓等人 提出来基于Ic一着色和干扰温度模型的差分调频系统多址原理，用IC-着色与干扰温度 理论控制网内用户的发射行为，使之达到区分预期信号和干扰信号的目的。SalehiE等人 于2005年引入了 图的Ic一着色的概念并得到了一些结果。 定义1 设G=(V,E)是一个图， 是正整数集。 = ： }， 是定义在 上的，取值在Ⅳ的函 数，若对于任意两个相连的点 和 ，，／()不等于f(vj)，则称 ／是G的一个着色。 定义 2 设 图G是一个连通 图 ，对于 图 G的一个着色 ，和 图G的一个 子 图，则记 f(H)=∑厂()，∈V(H)，特别的将f(G)记作s(f)。如果对于任意整数 ∈{l，2，3，…t厂(G)}，存在G的一个 连通子图H，使得f(H)=，则称／为图G的一个Ic一着色。并定义M(G)=max{f(G)}为图G的IC一指数， 并且称适合f(G)=M(G)的Ic一着色．厂为图G的一个极大Ic一着色。 由定义易得，一个图G存在Ic一着色的必要条件是G为连通图。 定义3 棒棒糖图 是由圈c上的任一个顶点和路P 的一个1度顶点重合而得到 +m一1阶的连 通 图。 一 般地说，确定一个图的Ic一指数是困难的，由文献 [5，7—13]已知一些图的IC-指数：完全图 ，星 K一完全二部图 圈c，路P ，K—e(表示减掉一条边的凡阶完全图)，双星图DS(m，)(由两个星图 K 和 的中心连一条新边得到的图)，其结果如下： 收稿 日期：2014—06—27 基金项目：国家自然科学基金；国家大学生创新创业训练计划项 目(201310699069) 作者简介：张楚文(1992一)，男，主要研究方向为计算机网络。 通迅作者：王力工 (1968一 )，男，教授，博士生导师，主要研究方向为图论及其应用。 第6期 张楚文，等：棒棒糖图的Ic一着色和Ic一指数 1) M(K)=2n一1； 的最大着色：(1，2，4，8，．．．，2n一1)。 2)nM(K3一e)=6； (—e)=2一3， ≥4。 3) 当n∈{3，4，5，6，8，9，10，12，14}时，则M(C)=n(n一1)+1。 4) (，)=2+2，2≤ 。 5) (Kml；)=3×2 ’一2一+2，2≤m≤n。 ． 的最大着色 ，K…的顶点二划分(，y)，其中 = 。，… )，y={y。，Y，．．．，Yl。 ff(x)=ldC(x)=2dC(y)=3 lf(Y)