图上随机游动和图的中间特征值研究

The study of random walks on graphs is an active interdisciplinary research area in graph theory and probability theory, and the study of median eigenvalues of graphs which have important applications in chemistry is in urgent need to develop. In this project, we will study some important problems in both research areas. On one hand, by electrical network approach, we will give quantitative characterization to random walks on composite graphs as well as graphs formed by unary operations; determine the exact variation of expected hitting times and expected commute times when small change is made on the graph; study the conjecture on the lower bound for partial sums of expected hitting times and give upper bound to it. On the other hand, we will estimate median eigenvalues of fullerenes on surfaces; study Mohar’s conjecture on median eigenvalues of planar subcubic graphs；characterize extremal graphs for bipartite graphs with unique perfect matching and graphs with unique Sachs subgraph with respect to median eigenvalues. The study will reveal the nature of random walks on various classes of graphs, and lay a solid theoretical foundation for understanding random walk on these graphs. In addition, the project will greatly enrich the system of theories and methodologies for the study of median eigenvalues of graphs, and provide reliable theoretical reference for Hückle molecular orbital theory.

图上随机游动是一个活跃的图论与概率论的交叉研究领域，而图的中间特征值是一个具有重要化学应用背景且亟待发展的研究领域。本课题将对这两个研究领域中的若干重要问题进行研究。一方面，利用电网络方法，我们将给出合成图和一元运算图上随机游动行为的定量刻画，确定图上发生微小变化后平均首达时间和平均往返时间的变化量的精确值，研究关于平均首达时间的部分和的下界的猜想并进一步确定其上界。另一方面，我们将估计曲面富勒烯图的中间特征值，研究Mohar提出的关于平面subcubic图的中间特征值的猜想，刻画具有唯一完美匹配的二部图和具有唯一Sachs子图的图的中间特征值的极值图。该研究将深刻揭示出若干图类上的随机游动行为的本质，为理解这些图上的随机游动行为奠定坚实的理论基础；同时，该研究还将极大丰富和发展图的中间特征值研究的理论体系和方法体系，并为Hückle分子轨道理论提供可靠的理论参考。

图上随机游动是一个经典交叉研究领域，和电网络之间有着密切的联系。图的中间特征值的研究源于化学中HOMO-LUMO能隙，其研究不仅具有重要的理论意义而且具有重要的应用背景。本项目围绕图的中间特征值和图上随机游动开展了深入的研究工作。在图的中间特征值研究方面，我们创新性地发展出了根据原图的逆图中的正子图和负子图来估计中间特征值的新方法，为图的中间特征值的研究提供了新的理论工具。应用此方法，我们证明了树的星状图、任意图的冠图、至多具有一个完美匹配的二部图的中间特征值均在[-1,1]的范围内，推广了Fowler和Pisanski的结果。此外，我们巧妙地给出了一种构造中间特征值尽可能小的图的构造方法，建立了分裂图和原图的HOMO-LUMO能隙之间的关系。特别地，我们完全解决了Godsil提出的长达30多年之久的一个公开问题，给出了具有唯一完美匹配的二部图的完整刻画，为研究具有唯一完美匹配的二部图的中间特征值奠定了坚实基础。在图上随机游动和电网络的研究方面，我们在图上随机游动平均首达时间的部分和猜想研究方面取得重要进展；得到了几类运算图上的电阻距离及随机游动的往返时间和平均首达时间；得到了备受关注的六角链图的电阻距离的精确解；还完全解决了2011年提出的关于基尔霍夫指标的Nordhaus-Gaddum型结果的一个重要猜想。此外，本项目在广义斐波那契立方体和广义卢卡斯立方在超立方中的等距离嵌入的研究方面取得系列重要研究成果。本项目的研究成果为相关领域的研究工作起到了积极的推动作用。在本项目的资助下，我们在Combinatorica等国际权威学术期刊发表SCI论文21篇；培养硕士研究生15人，其中毕业4人，目前在读11人；项目负责人获得山东省优秀青年基金资助，并应邀在运筹千里纵横论坛（第九期）暨中国运筹青年论坛（山东）做学术报告。