图的匹配强迫与匹配阻碍问题研究

This project mainly studies the matching forcing and matching preclusion problems of graphs, including forcing numbers of perfect matchings of a graph and their distribution, global forcing number, total forcing number, anti-forcing number, matching preclusion, and so on. In details, we shall discuss relationships between forcing number and the maximum number of independent conjugated circuits (resp. faces) for perfect matchings of graphs; We investigate the distribution of forcing numbers of perfect matchings and the continuity and gap situation of forcing spectrum, compute the matching forcing polynomial of some graphs, in particular, we will solve the Pachter and Kim's conjecture by obtaining the minimum forcing number of general hypercubes, and find out some types of graphs with the continuous forcing spectrum in hexagonal systems, fullerenes,and so on, by matching-switches on conjugated circuits; We seek some research approaches for global forcing number, total forcing number, anti-forcing number and matching preclusion number (including the anti-Kekulé number) of graphs and their computational complexities as well. Matching forcing and matching preclusion problems of graphs originated from the theoretical chemistry and computer networks have been studied recently in mathematics, and are a new development direction of matching theory of graphs. Some challenging problems have been put forward, and many basic problems need solutions. Systematical studies of this project can produce some valuable research methods, and solve some important problems. The implementation of this project can lay the research foundation for this new direction of matching theory, and push forward a new development of matching theory of graphs.

本项目主要研究图的匹配强迫和匹配阻碍问题，包括图的完美匹配的强迫数及其分布，全局强迫数和完全强迫数，反强迫数和匹配阻碍等。具体地讨论图的完美匹配的强迫数与独立交错圈、独立交错面的最大个数之间的关系;研究图的匹配强迫数分布和强迫谱这个整数集的连续和间断情况, 计算若干图的匹配强迫多项式，特别是得到超立方图的最小强迫数以证实Pachter 和Kim的猜想，利用图的共振圈的变换方法发现六角系统和Fullerene等图中具有连续强迫谱的类型；讨论全局强迫数和完全强迫数、反强迫数和各种匹配阻碍数（包括反Kekulé数）的计算方法和计算复杂性. 图的匹配强迫和匹配阻碍问题来源于理论化学和计算机网络, 是匹配理论发展的新方向，一些挑战性问题相继被提出，许多基本问题亟待解决. 通过本项目的研究提出有价值的研究方法，解决若干重要问题,为这个匹配理论的新型领域的研究奠定基础, 推动匹配理论的进一步发展.

本项目主要研究图匹配强迫和匹配阻碍问题, 其来源于理论化学和计算机网络, 包括平面二部图的完美匹配的强迫与反强迫和交错面集的极大极小关系, 匹配强迫数与反强迫数及其分布, 完全强迫数和匹配阻碍等, 是图的匹配理论发展的新方向. 在强迫数与共轭圈的关系上, 表明了对六角系统与方格子图达到最大强迫数的每个完美匹配都有最多的独立交错面的个数,（4,6)-fullerene图的最大强迫数等于共振数(或Clar 数); 在匹配强迫数的分布上，借助Z-变换图（或共振图）的连通性表明有强迫边的六角系统的强迫谱是连续的（最多2是间隔), 偶阶路与奇长圈的卡氏积图（柱面格子图）的强迫谱是连续的, 广义彼得森图P(n,2)的强迫谱是两个整区间的并. 对zigzag六角链、冠状六角环、cata型和和平行四边形六角系统计算出了它们的强迫多项式, 得到平均强迫数的一些渐进结果. 利用构造方法刻画出了最小强迫数是3的所有富勒烯图，解决了一公开问题；提出并研究了图的完全强迫数，刻画出了其完全强迫集，给出cata型苯系统的完全强迫数的线性算法，表明其完全强迫数等于Clar数加上六边形的个数，给出了渺位冠状系统的完全强迫数的精确表达式；在反强迫上，提出了图的单个完美匹配的反强迫数，极大扩展了D. Vukicvic 与N. Trinajstic 的起初概念，建立了与强迫数的关系，揭示出了与强迫数类似的极大极小结果，证明了六角系统与(4,6)-fullerene图的最大反强迫数都等于各自的Fries数. 给出了图的最大反强迫数的两个可达上界并刻画出了极值图. 证明了Cata型与单调可构造型六角系统的反强迫谱是连续的. 在匹配阻碍上，研究了偶阶点传递图与正则图的极大匹配与超匹配性，统一得到了一系列已知结果. 将图的匹配排除数表示成线性整数规划，利用完美匹配多面体理论研究分数匹配排除数, 证明了一般图分数匹配排除数有多项式时间算法. 对于二部图，给出了其显式表达式，并与k-因子建立了联系. 表明了一般正则图与极大匹配正则图的笛卡尔乘积图、直积图与强乘积图都是超匹配的.