无爪3 -正则图的独立数

数学物理学报

无爪3 -正则图的独立数

王春香

(华中师范大学数学与统计学院武汉 430079)

收稿日期:2006-06-21 修回日期:2007-09-20 出版日期:2009-02-25 发布日期:2009-02-25
通讯作者: 王春香
基金资助:
国家自然科学基金（10571071, 10671081）资助.

Independence Number in Claw-free Cubic Graphs

Wang Chunxiang

(Department of Mathematics, Huazhong Normal University, Wuhan 430079)

Received:2006-06-21 Revised:2007-09-20 Online:2009-02-25 Published:2009-02-25
Contact: Wang Chunxiang

摘要/Abstract

摘要： 如果图G的一个集合X中任两个点不相邻, 则称 X 为独立集合. 如果 N[X]=V(G), 则称X是一个控制集合. i(G)(β(G))分别表示所有极大独立集合的最小(最大)基数. γ(G)(Γ(G))表示所有极小控制集合的最小(最大)基数. 在这篇论文中, 作者证明如下结论: (1) 如果 G ∈R 且G 是n阶3 -正则图, 则 γ(G)= i(G), β(G)=n/3. (2) 每个n阶连通无爪3 -正则图 G, 如果 G(G≠ K₄)
且不含诱导子图K₄-e, 则 β(G) =n/3.

关键词: 3 -正则图, 控制数, 独立控制数, 着色.

Abstract: A set X is independent if no two vertices of X are adjacent. A set X is dominating if N[X]=V(G). A dominating set X is minimal if no set X\{x} with x∈ X
is dominating. The independence number i(G)(\beta(G)) is the minimum (maximum) cardinality of a maximal independent set of G. The domination number γ(G) (the upper domination number Γ(G)) is the minimum (maximum) cardinality of a minimal dominating set of G. In this paper, we prove that: (1) if G ∈ R and G is a cubic graph of order n, then γ(G)=i(G), β(G)=n/3; (2) for every connected claw-free cubic graph G of order n, if G(G≠ K₄) contains no K₄-e as induced subgraph, then β(G)=n/3.

Key words: Cubic graph, The domination number, The independence number, Colouring.

中图分类号:

王春香.

无爪3 -正则图的独立数

[J]. 数学物理学报, 2009, 29(1): 145-150.

Wang Chunxiang. Independence Number in Claw-free Cubic Graphs[J]. Acta mathematica scientia,Series A, 2009, 29(1): 145-150.

[1]	王春香, 李相文. 极大γ_t- 临界图[J]. 数学物理学报, 2009, 29(2): 297-302.
[2]	陈学刚; 孙良; 邢化明. 立方图的对控制数[J]. 数学物理学报, 2007, 27(1): 166-170.