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

路径幂图、Flower Snark图及多锥图独立数 被引量：1

Independence number of path power,Flower Snark and multi-cone graphs
下载PDF
导出
摘要 图的独立数是图论中的重要参数,令G=(V(G),E(G))是一个简单有限无向图.如果V(G)的子集S中任意两个顶点均不相邻,则S是图G的一个独立集.顶点独立集大小的最大值,称为图G的独立数,记做α(G).研究了路径幂图、Flower Snark及其相关图、多锥图的独立数问题,首先构造出了它们的独立集,得到其独立数的下界,然后证明了该值也是其独立数的上界,并给出了它们独立数的准确值. Independence number of the graph is an important parameter in graph theory. Let G=（V（G）,E（G）） be a simple finite undirected graph. A sub-set S of V（G） is an independent set and any two vertices of S aren＇t adjacent. So the independence number α（G） is the maximum cardinality of an independent set in G. The independence number of path power graph,Flower Shark and its related graph,multi-cone graph is studied. Firstly,the independent sets of them are constructed,so their lower bounds of the independence number are obtained. Secondly,it is proved that these bounds are also the upper bounds of those three graphs. Then,their exact values of the independence number are given.
作者 徐连诚 杨元生 夏尊铨
机构地区 大连理工大学数学科学学院 山东师范大学信息科学与工程学院 大连理工大学计算机科学与技术学院
出处 《大连理工大学学报》 EI CAS CSCD 北大核心 2010年第2期309-312,共4页 Journal of Dalian University of Technology
基金 国家自然科学基金资助项目(90612003)
关键词 独立集 独立数 路径幂图 FLOWER SNARK 多锥图 independent set independence number path power graph Flower Snark multi-cone graph
分类号 O157.5 [理学—基础数学]
  • 相关文献

参考文献11

  • 1WEST D B. Introduction to Graph Theory[M]. 2nd ed. Englewood Cliffs:Prentice Hall, 2001.
  • 2GUO S G. On the spectral radius of unicyclic graphs with n vertices and edge independence number q [J]. Ars Combinatoria, 2007, 83 : 279-287.
  • 3KLAVZAR S. Some new bounds and exact results on the independence number of Cartesian product graphs [J]. Ars Combinatoria, 2005, 74.. 173-186.
  • 4MARTIN S P, POWELLJ S, RALL DF. On the independence number of the Cartesian product of caterpillars [J]. Ars Combinatoria, 2001, 60:73-84.
  • 5PEPPER R. An upper bound on the independence number of benzenoid systems [J]. Discrete Applied Mathematics, 2008, 156(3) :607-619.
  • 6李雨生,C.C.Rousseau,臧文安.独立数的一个下界[J].中国科学（A辑）,2001,31(10):865-870. 被引量：4
  • 7LU M, LIU H Q, TIAN F. Laplacian spectral bounds for clique and independence numbers of graphs [J]. Journal of Combinatorial Theory Series B, 2007, 97(5) :726-732.
  • 8BERGER E, ZIV R. A note on the edge cover number and independence number in hypergraphs [J]. Discrete Mathematics, 2008, 308 (12) 2649-2654.
  • 9EGAWA Y, ENOMOTO H, JENDROL D Independence number and vertex-disjoint cycles [J]. Discrete Mathematics, 2007, 307(11-12) :1493-1498.
  • 10AMIN A T, HAKIMI S L. Upper bounds on the order of a clique of a graph [J]. SIAM Journal of Applied Mathematics, 1972, 22(4) : 569-573.

二级参考文献11

  • 1Alon N, Spencer J. The Probabilistic Method. New York: Wiley-Interscience, 1992
  • 2Ajtai M, Komls J, Szemerédi E. A note on Ramsey numbers. J Combin Theory Ser A, 1980, 29: 354-360
  • 3Shearer J. A note on the independence number of triangle-free graphs. Discrete Math, 1983, 46: 83～87
  • 4Kim J. The Ramsey number R(3,t) has order of magnitude t2/logt. Random Structures Algorithms, 1995, 7: 174～207
  • 5Tardos E. 1997 Fulkerson prize. Notices of American Math Soc, 1998, 45(8): 984
  • 6Griggs J. Lower bounds on the independence number in term of the degrees, J Combin Theory Ser B, 1983, 34: 22～29
  • 7Li Y, Rousseau C. Fan-complete graph Ramsey numbers. J Graph Theory, 1996, 23: 413～420
  • 8Shearer J. A note on the independence number of triangle-free graphs Ⅱ. J Combin Theory Ser B, 1991, 53: 300～307
  • 9Li Y, Rousseau C. On book-complete Ramsey numbers. J Combin Theory Ser B, 1996, 68: 36～44
  • 10Li Y, Rousseau C, Zang W. Asymptotic upper bounds for Ramsey functions. Graphs Combin, 2001, 17: 123～128

共引文献3

同被引文献2

引证文献1

大连理工大学学报
2010年 第2期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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