双星图的IC-着色

陈剑峰,杨大庆

(1.湄洲湾职业技术学院基础部,福建 莆田 351254;福州大学数学与计算机科学学院,福建 福州 351108)

双星图的IC-着色

陈剑峰1,杨大庆2

(1.湄洲湾职业技术学院基础部,福建 莆田 351254;福州大学数学与计算机科学学院,福建 福州 351108)

研究了双星图的IC-着色问题,得到了双星图极大IC-着色的一些必要条件.利用这些必要条件,得到了双星图的极大IC-着色至多有两类着色方案,并确定了双星图在其中一种情况下的IC-指数.

IC-着色;IC-指数;双星图

1 引言

2 一些引理

利用计算机,可以得到m+n≤7时,M(DS(m,n))=(2m-1+1)(2n-1+1),其中2≤m≤n. m+n≤7时,DS(m,n)所有的极大IC-着色如图1所示.

图1 m+n≤7时DS(m,n)的极大IC-着色

引理2.4[8]设f是图G的一个IC-着色,G有ℓ个连通子图.如果图数值相同的连通子图重复了k次,则S(f)≤ℓ-k.

引理2.5设2≤m≤n时,则图DS(m,n)共有(2m-1+1)(2n-1+1)+m+n-3个不同的连通子图.

证明设H是图DS(m,n)的连通子图,则有下面几种情况:(1)V(H)⊂L或V(H)⊂R; (2)V(H)⊂(L∪{u});(3)V(H)⊂(R∪{v});(4){u,v}⊂V(H).

所以图DS(m,n)不同的连通子图H的个数为:

3 主要结果

[1] Bondy J A, Murty U S R. Graph Throry[M]. Berlin: Springer, 2008.

[2] Alter R, Brnett J A. A postage stamp problem[J]. Amer. Math. Monthly., 1980,87:206-210.

[3] Heimer R L, Langenbach H. The stamp problem[J]. J. Recreational. Math., 1974,7:235-250.

[4] Lunnon W F. A postage stamp problem[J]. Comput. J., 1969,12:377-380.

[5] Penrice S G. Some New Graph Labeling Problems: a Preliminary Report[C]. New York: Cortland, 1995.

[6] Salehi E, Lee S, Khatirinejad M. IC-colorings and IC-indices of graphs[J]. Discrete Mathematics, 2005,299:297-310.

[7] 徐宝根.关于连通图的IC-着色[J].华东交通大学学报,2006,23(1):134-136.

[8] Shiue C L, Fu H L. The IC-indices of complete bipartite graphs[J]. Electronic Journal of Combinatorics, 2008,15:43-49.

[9] 陈剑峰.笛卡尔积图Pm×Pn的IC-着色[J].莆田学院学报,2011,18(2):13-15.

[10] 程卓,王殊.基于IC着色的认知差分跳频系统多址原理[J].武汉大学学报:理学版,2010,56(4):478-482.

The IC-colorings of double-stars

Chen Jianfeng1,Yang Daqing2

(1. Foundation Department, Meizhouwan Vocational and Technology College, Putian 351254, China; 2. Colloge of Mathenematics and Computer Science, Fuzhou University, Fuzhou 351108, China)

This article got some necessary conditions of the double-stars maximum IC-coloring by taking a study on the problem. In use of these necessary conditions, we can got at least two coloring schemes of the double-stars maximum IC-coloring and be certain of the double-stars IC-index in one of the condition.

IC-coloring,IC-index,double-stars

O 157.5

A

1008-5513(2012)02-0201-12

2011-08-05.

福建省教育厅重点项目(JA 10018).

陈剑峰(1980-),硕士,讲师,研究方向：图论.

2010 MSC:05C78