雙星圖的IC-著色

陳劍峰,楊大慶

(1.湄洲灣職業(yè)技術學院基礎部,福建 莆田 351254;福州大學數(shù)學與計算機科學學院,福建 福州 351108)

雙星圖的IC-著色

陳劍峰1,楊大慶2

(1.湄洲灣職業(yè)技術學院基礎部,福建 莆田 351254;福州大學數(shù)學與計算機科學學院,福建 福州 351108)

研究了雙星圖的IC-著色問題,得到了雙星圖極大IC-著色的一些必要條件.利用這些必要條件,得到了雙星圖的極大IC-著色至多有兩類著色方案,并確定了雙星圖在其中一種情況下的IC-指數(shù).

IC-著色;IC-指數(shù);雙星圖

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有?個連通子圖.如果圖數(shù)值相同的連通子圖重復了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的個數(shù)為:

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著色的認知差分跳頻系統(tǒng)多址原理[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