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

正则图的团横贯数的界 被引量：1

原文传递
导出
摘要 设D是图G的一个顶点子集,若D含有G的每个团中至少一个顶点,则D称为G的团横贯集.图G的团横贯数是指它的最小团横贯集中顶点的数目,记作T_c(G).本文研究正则图的团横贯数.首先建立了正则图的团横贯数的上、下界,且刻画了达到下界的极值图.其次,对无爪三次图,得到了改进的可达上、下界并刻画了达到下界的极值图.
作者 单而芳 郑大昭 康丽英
机构地区 上海大学理学院数学系 香港理工大学物流系
出处 《中国科学（A辑）》 CSCD 北大核心 2007年第11期1257-1268,共12页 Science in China(Series A)
基金 国家自然科学基金(批准号:10571117 60773078) 香港理工大学博士后基金(批准号:G-YX69) 上海市曙光计划(批准号:06SG42)资助项目
关键词 图 正则图 无爪三次图 团横贯集 团横贯数
分类号 O157.5 [理学—基础数学]
  • 相关文献

参考文献22

  • 1Bondy J A, Murty U S R. Graph Theory with Applications. New York: Elsevier, 1976
  • 2Berge C. Graphs and Hypergraphs. Amsterdam: North-Holland, 1973
  • 3Andreae T, Schughart M, Tuza Z. Clique-transversal sets of line graphs and complements of line graphs. Discrete Math, 88:11-20 (1991)
  • 4Haynes T W, Hedetniemi S T, Slater P J. Fundamentals of Domination in Graphs. New York: Marcel Dekker, 1998
  • 5Erdos P, Gallai T, Tuza T. Covering the cliques of a graph with vertices. Discrete Math, 108:279-289 (1992)
  • 6Chang G J, Farber M, Tuza Z. Algorithmic aspects of neighbourhood numbers. SIAM J Discrete Math, 6: 24-29 (1993)
  • 7Guruswami V, Rangan C P. Algorithmic aspects of clique-transversal and clique-independent sets. Discrete Appl Math, 100:183-202 (2000)
  • 8Chang M S, Chen Y H, Chang G J, et al. Algorithmic aspects of the generalized clique-transversal problem on chordal graphs. Discrete Appl Math, 66:189-203 (1996)
  • 9Balachandhran V, Nagavamsi P, Ragan C P. Clique transversal and clique independence on comparability graphs. Inform Process Lett, 58:181-184 (1996)
  • 10Lee C M, Chang M S. Distance-hereditary graphs are clique-perfect. Discrete Appl Math, 154:525-536 (2006)

同被引文献8

  • 1Folkerts M (ed), Alcuin F. Propositiones ad Acuendos hvenes (reprinted). Berlin: Springer, 1978.
  • 2Prisner E. Generalizing the wolf-goat-cabbage problem. Electron Notes Discrete Math, 2006, 27:83.
  • 3Csorba P, Hurkens C A J, Woeginger C J. The Alcuin number of a graph and its connections to the vertex cover number. SIAM Rev, 2012, 54:141-154.
  • 4Lampis M, Mitsou V. The ferry cover problem. In: Lecture Notes in Comput Sci, vol. 4475. Berlin: Springer, 2007, 227-239.
  • 5Csorba P, Hurkens C A J, Woeginger C J. The Alcuin number of a graph and its connections to the vertex cover number. SIAM J Discrete Math, 2010, 24:757-769.
  • 6Shan E F, Kang L Y. The Alcuin number of a graph with small maximum degree. SIAM J Discrete Math, in press, 2013.
  • 7Bondy J A, Murty U S R. Graph Theory. Berlin: Springer, 2008.
  • 8冯弢,柴钊,常彦勋.完全3-一致超图的一类填充问题和覆盖问题[J].中国科学：数学,2012,42(6):619-633. 被引量：2

引证文献1

二级引证文献2

中国科学（A辑）
2007年 第11期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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