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

二部图匹配强迫数的谱 被引量：2

On the spectrum of matching forcing numbers for bipartite graphs
原文传递
导出
摘要 改进了Riddle的尾点法,得到自然数k属于二部图匹配强迫数谱的必要条件,给出了二部图的最小强迫数等于一个颜色集所有规范序最小尾点数的充要条件。 The trailing-vertex method in essence is improved,a necessary condition for the forcing number of perfect matching equals to a given natural number k for a bipartite graph is obtained,and a necessary and sufficient condition for the minimum forcing number equals the minimum number of trailing vertices of all standard orderings of a color set is given.
作者 王洪伟
机构地区 临沂师范学院理学院
出处 《山东大学学报（理学版）》 CAS CSCD 北大核心 2009年第12期30-35,40,共7页 Journal of Shandong University(Natural Science)
基金 临沂师范学院博士科研启动基金资助项目(BS08027)
关键词 二部图 完美匹配 强迫数 NP-完全问题 bipartite graph perfect matching forcing number NP-complete
分类号 O157.5 [理学—基础数学]
  • 相关文献

参考文献17

  • 1HARARY F, KLEIN D J, ZIVKOVIC T P. Graphical properties of pelyhexes: perfect matching vector and forcing[J]. J Math Chem, 1991, 6:295-306.
  • 2KLEIN D J, RANDIC M. Irmate degree of freedom of a graph [J]. J Comput Chem, 1987, 8:516-521.
  • 3SHIU W C, ZHANG Heping. Acomplete characterization for k-resonant Klein-bottle polyhexes [J]. J Math Chem, 2008, 43( 1 ) :45-59.
  • 4VUKICEVIC D, SEDLAR J. Total forcing number of the triangular grid[J]. Mathematical Communications, 2004, 9: 169-179.
  • 5CHE Z, CHEN Z. Forcing hexagons in hexagonal systems[J]. MATCH Commun Math Comput Chem, 2006, 56(3) :649-668.
  • 6VUKICEVIEVIC D, TRINAJSTIC N. On the anti-Kekule number and anti-forcing number of cata-condensed benzenoids [J]. J Math chem, 2008, 43(2):719-726.
  • 7WANG H, YE D, ZHANG H. The forcing number of toroidal polyhexes[J]. J Math Chem, 2008, 43(2) : 457-475.
  • 8RANDIC M. Aromaticity of polycychc conjugated hydrocarbons [ J]. Chem Reviews, 2003, 103 (9): 3449-3605.
  • 9RANDIC M, KLEIN D J. Mathematics and Computational Concepts in Chemistry[M]. New York: Horwood, Halsted Press, 1986:274- 282.
  • 10BONDY J A, MURTY U S R. Graph Theory[M]. New York: Springer, 2008.

同被引文献26

  • 1Pauling L. The Nature of Chemical Bond, Cornell [M]. New York : Ithaca Univ Press, 19 3 9.
  • 2Kasteleyn P W. Graph Theory and Crystal Physics [C]//Graph Theory and Theoretical Physics. Lon- don : Academic Press, 1967 : 43-110.
  • 3Halt G G. A graphic model of a class of molecules[J]. Int J Math Edu Sci Techno1,1973 ,4( 3 ) :233-240.
  • 4Swinborne-Sheldrake R, Herndon W C, Gutman T. Kekule structures and resonance energies of benzennoid hydrocarbons [C]//Tetrahedron Lett. Oxfod~ Perga- mon-Elsevier Science Ltd, 1975:755-758.
  • 5Valiant L G. The complexsity of computing the perma- nent[J]. Theoretical Compute Science, 1979,8(2) : 189- 201.
  • 6Lovdsz L, Plummer M. Matching Theory[M]. New York: North-Holland Press, 1986.
  • 7张福基,陈荣斯.六角系统克库勒结构的计数[J].新疆大学学报(自然科学版),1986,3(3):10-14.
  • 8张福基,陈治柏.广义渺位苯图的完美匹配数的计算[J].新疆大学学报(自然科学版),1986,3(3):6-10.
  • 9Zhang Heping. The connectivity of Z-transformation graphs of perfect matchings of polyominoes[J]. Dis- crete Mathematics, 1996,158 : 257-272.
  • 10Zhang Heping, Zhang Fuji, Perfect matchings of polyomino graphs [J]. Graphs and Combinatorics, 1997,13:259-304.

引证文献2

二级引证文献22

山东大学学报（理学版）
2009年 第12期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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