关于匹配数的图能量的下界

发布时间：2020-02-17 09:21

【摘要】：图G的能量ε(G)是G中所有特征值的绝对值之和,记作ε(G)=(?).我们用V(G)和E(G)分别表示G的顶点集和边集.图G中的匹配M是指成对的非相邻边的集合,也就是说M中任意两条边都没有公共顶点.最大匹配是指包含边数最多的匹配,最大匹配中的边的数目叫作G的匹配数,记作u(G).本篇文章中我们关注于图G的能量和匹配数μ(G)之间的关系,我们证明了对于每一个图G有ε(G)≥2μ(G),且ε(G)≥2μ(G)+(?)c1(G).其中G中的圈(如果存在)是顶点两两不相交的,c1(G)表示G中奇圈的个数.此外,我们证明了如果G有至少一个奇圈且不是满秩的,则ε(G)≥r(G)+1/2.本文主要研究关于匹配数的图能量的下界,全文共分为五章.第一章是绪论部分,主要介绍了论文的选题背景,课题的研究现状和一些重要的符号知识.第二章介绍了相关概念和与本文有关的已知结论.第三章主要研究了关于秩的图能量的新界.第四章主要证明了关于匹配数的图能量的下界的两个重要结论.第五章总结了本篇论文的主要内容,并提出了今后进一步的研究目标。
【图文】：

割集,匹配数,最大匹配,不等式

H 是匹配数为 1的图, (G ) 2 (H)成令M 是G 的最大匹配,含有条边 e ,e12的集合.则E 是满足 2G E K G K()12 G K ,2G K中可推出 ()212 G K .可得 22122G E K G K 求不等式 G G E 2.

割集,归纳假设,引理,条件

图 4-3 删除图中一个割集 4-3 Demonstration of deleting a cut edge from G e G G e 1. G e,由于 G H K,c1条件(归纳假设),则应用引理 4.5 可得 G e 1,等价于e属于G 的每一个最 G H x 1 K y. x 1 K y.则 G H x K x. G H y K y.
【学位授予单位】：中国矿业大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【参考文献】