期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

有关循环图C(n;{1,k})的独立数的一些结果(英文)

Some Results on the Independence Number of Circulant Graphs C(n;{1,k})
下载PDF
导出
摘要 令G=(V(G),E(G))是一个简单有限无向图.如果V(G)的子集S中任意两个顶点均不相邻,则S是图G的一个独立集.顶点独立集大小的最大值,称为图G的独立数,记作α(G).本文研究了循环图C(n;{1,k})的独立数问题,并给出了当k=2,3,4,5时的准确值. Let G = （V（G）, E（G）） be a simple finite undirected graph. A set S lohtain .in V（G） is an independent set if no twovertices of S are adjacent. The independence number α（G） is the maximum cardinality of an independent set in G. In this paper, we study the independence number of the circulant graphs, and give the exact values of C（n; {1, k}） for k= 2,3,4,5.
作者 徐连诚 夏尊铨 杨元生
机构地区 大连理工大学应用数学系 大连理工大学计算机科学与工程系
出处 《运筹学学报》 CSCD 2009年第4期65-70,共6页 Operations Research Transactions
基金 Supported by National Science Foundation of China,Grant 90612003
关键词 运筹学 图论 独立集 独立数 循环图 Operations research, graph theory, independent set, independence number, circulant graph
分类号 O157.5 [理学—基础数学] O171 [理学—基础数学]
  • 相关文献

参考文献13

  • 1D.B. West. Introduction to Graph Theory, Second Edition[M]. Englewood Cliffs, N J: Prentice Hall, 2001.
  • 2徐新萍.独立集的度和与图的哈密尔顿性[J].运筹学学报,2006,10(3):109-113. 被引量：1
  • 3皮军德,康丽英,许光俊.直线簇上区间图的最小独立控制集[J].运筹学学报,2006,10(1):107-115. 被引量：2
  • 4S.G. Guo. On the spectral radius of unicyclic graphs with n vertices and edge independence number q[J]. Ars Combinatoria, 2007, 83: 279-287.
  • 5Sandi Klavzar. Some new bounds and exact results on the independence number of Cartesian product graphs[J]. Ars Combinatoria, 2005, 74: 173-186.
  • 6S.P. Martin, J.S. Powell,D.F. Rall. On the independence number of the Cartesian product of caterpillars[J]. Ars Combinatoria, 2001, 60: 73-84.
  • 7Ryan Pepper. An upper bound on the independence number of benzenoid systems[J]. Discrete Applied Mathematics, 2008, 156(5): 607-619.
  • 8Yusheng Li, C.C. Rousseau, Wen'an Zhang. The lower bound on independence number.[J] Science in China, Series A, 2002, 45(1): 64-69.
  • 9Mei Lu, Huiqing Liu, Feng Tian. Laplacian spectral bounds for clique and independence numbers of graphs[J]. Journal of Combinatorial Theory, Series B, 2007, 97(5): 726-732.
  • 10Eli Berger, Ran Ziv. A note on the edge cover number and independence number in hypergraphs[J]. Discrete Mathematics, 2008, 308(12): 2649-2654.

二级参考文献14

  • 1S.W.Cheng,M.Kaminski,S.Zads.Minimum dominating sets of intervals on lines.Algorithmica,1998,20:294～308.
  • 2M.C.Golumbic.Algorithmic Graph Theory and Perfect Graphs,Academic Press,New York,1980.
  • 3E.McCreight.Priority search trees.SIAM J.Comput.,1985,14:257～276.
  • 4G.Ramalingam,P.Rangan.A unified approach to domination problems on interval graphs.Inform.Process.Lett.,1988,27:271～274.
  • 5A.Bertossi,A.Gori.Total domination and irredundance in weighted interval graphs.SIAM J.Discrete Math.,1988,3:317～327.
  • 6B.Bollobás.Modern Graph Theory[M].New York:Spring-Verlag,2001.
  • 7K.Booth,J.Johnson.Dominating sets in chordal graphs.SIAM J.Comput.,1982,11:191～199.
  • 8K.Booth,G.Leuker.Testing for consecutive ones property,interval graph,and graph planarity using PQ-tree algorithms.J.Comput.System Sci.1976,13:335～379.
  • 9A.Brandtstaedt.The computational complexity of feedback vertex set,hamiltonian circuit,dominating set,steinertree,and bandwidth on special perfect graphs.J.Inform.Process.Cybern.,1987,23:471～474.
  • 10M.S.Chang.Efficient algorithms for the domination problems on interval and circular-arc graphs,SIAM J.Comput.,1998,6:1671～1694.

共引文献1

运筹学学报
2009年 第4期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部