论文部分内容阅读
本论文在前人研究的基础上,进一步研究了几类图独立集,匹配和极大独立集的计数问题.主要内容包括:
(1)在第一节和第二节介绍了本文研究的背景和研究意义,以及国内外在这方面具有代表性的发展状况.通过对本文研究背景及研究现状的深刻讨论,充分说明了本文的主要研究工作的必要性和创新性.最后,给出了本文涉及到的部分记号和引用的引理.
(2)在第三节,我们主要对双圈图的独立集计数进行了研究,给出了双圈图独立集的上下界,并给出了达到上下界时对应的图;
(3)在第四节,我们主要对quasi-树图的独立集计数和匹配计数进行了研究,给出了第一大,第二大上界和第一小,第二小下界,对应的极图也进行了刻画,同时我们也给出了含k个叶子的quasi-树的匹配计数的下界及其对应的极图;
(4)在第五节,我们主要对圈秩个数至多为2的连通图的极大独立集计数进行了刻画,给出了上界,并刻画了达到上界时对应的图;
(5)在第六节,我们主要在G.C.Ying,K.K.Meng,B.E.Sagan和V.R.Vatter[Maxi-mal independent sets in graphs with at most r cycles,J.Graph Theory,53(2006),270-282]的基础上,对至多有r个圈的图第二大极大独立集计数进行了刻画,给出了极大独立集达到第二大的界,对应的给出了达到第二大界的图。