曲面嵌入图的匹配扩张

This project mainly studies the problem of characterizing all the graphs in surfaces with the maximum extendability and discuss the relationship between cyclic edge-connectivity and matching extendability of graphs in surfaces. In details, we will characterize all the graphs in the Klein bottle with the maximum extendability based on the complete characterization of all the graphs in the Torus with the maximum extendability; We shall discuss the relationship between cyclic edge-connectivity and 2-extendability for cubic graphs in surfaces; We investigate the cubic cyclic 5-edge connected projective graphs, characterize the structure of this kind of graphs, present the relationship between the non-2-extendable graphs in this class and the Petersen minor, as an application, we are going to determine all the 2-extendable graphs in projective fullerenes. Consequently, the problem of characterizing 2-extendable graphs among fullerenes in surfaces is completely solved. M.D. Plummer, a famous graph theorist, has shown that for a given surface, the matching extendability of any graph embedded in it has an upper bound related to its genus. Motivated by this, he put forward the problem of determining the matching extendability of surfaces. N. Dean presents a nice expression of the matching extendability of surfaces by using their Euler characteristic. The matching extendability of a surface reveals the maximum extendability among graphs in this surface.

本项目主要研究曲面上达到最大匹配可扩度的图的刻画问题以及曲面上图的环边连通性和可扩性的关系. 具体地, 在完整刻画环面上达到最大匹配可扩度的图的基础上, 刻画 Klein 瓶上达到最大匹配可扩度的图; 讨论曲面上三正则图环边连通性和 2-可扩性的关系; 研究射影平面上三正则环 5-边连通图, 刻画这类图的结构, 找出此类图中非 2-可扩图和 Petersen minor 的关系, 作为应用, 确定射影平面富勒烯图中 2-可扩图类. 由此, 完整解决曲面富勒烯图的 2-可扩性刻画问题. 著名图论专家 M.D. Plummer 表明嵌入在任意曲面上的图的匹配可扩度有上界. 由此, 提出确定曲面匹配可扩度的问题. N. Dean用欧拉示性数给出了曲面匹配可扩度的简洁的表达式. 曲面的匹配可扩度揭示了此曲面上图的匹配可扩度的最大程度.

图的匹配理论来源于现实生活中的人员安排，化学中的 Kekulé 结构， 统计物理中的 Dimer 问题等, 具有广泛的应用背景，目前已发展成为图论中一个重要分支。近期，匹配扩张和匹配排除理论等成为匹配理论中热门的研究方向。Dean 证明了环面和 Klein 瓶上的图最多是 3-可扩的。项目负责人在与 Aldred, Plummer 以及叶东和张和平教授的合作下，完整刻画了环面上 3-可扩图。在此基础上，本项目首先刻画了 Klein 瓶上的所有 3-可扩图。其次，在对匹配可扩性的讨论中, 图参数环边连通性起着重要的作用. 对一般三正则图， 环边连通性不能保证 2-可扩性。 对曲面三正则图,，我们表明除射影平面外，足够大的环边连通度可以保证 2-可扩性。接着对射影平面上三正则环 5-边连通图的 2-可扩性进行讨论。因这类图包含射影平面富勒烯图类，我们单独研究了射影平面富勒烯图的 2-可扩性。在完成了上述主要研究工作的的同时，我们还进行了项目以外的其它相关研究。主要有：刻画了 2-可扩的拟交换群上 Cayley 图；研究了三正则图的反凯库勒数和最小反凯库勒集；刻画了2-可扩的三正则和四正则点可迁图；完整解决了点可迁图的匹配排除问题；完整解决了立方体互联圈的匹配排除问题和限制匹配排除问题；首次提出了 Lanzhou index 的概念并刻画了几类图中的极值情况；给出了一般 polynomino 的饱和数的上下界; 在树中和单圈图中分别刻画了所有的等可匹配图和几乎等可匹配图等。