基于Laplace矩阵、正规化Laplace矩阵的图结构与图参数的研究

The spectral graph theory is an important research field in graph theory. The Laplacian and normalized Laplacian matrix of graphs are closely related to many useful parameters such as the expected hitting time, the resistance distance, the Kirchhoff index, Multiplicative degree-Kirchhoff index, the number of spanning tree and the Laplacian energy. Studying these parameters not only promotes the development of spectral graph theory, but also affords a strong tool for applying these theories to many other research fields. So the research on these parameters is a very popular research topic. .In this project, we mainly study graph structures and parameters based on the Laplacian and normalized Laplacian matrices of graphs. The main content of this project contains the following: Firstly, we mainly study formulas for the Kirchhoff index, multiplicative degree-Kirchhoff index, and number of spanning trees of some special graphs by considering the Laplacian and normalized Laplacian matrix of these graphs. Secondly, study the extremal problems based on the expected hitting time ,cover cost, reverse cover cost. Finally, study the energy and Laplacian energy of signed random graph. In conclusion, the research of this project will extend the connotation of the study on spectral graph theory, extremal graph theory and random graph theory, which will improve the research level of algebraic graph theory and combinatorial matrix theory in China.

图谱理论是图论的一个重要研究分支。图的Laplace矩阵和正规化Laplace矩阵与图的一些参数比如hitting time期望值、电阻距离、基尔霍夫指数、度积-基尔霍夫指数、生成树数目以及Laplace能量等都密切相关。研究这些参数与图结构的联系不仅能大力促进图谱理论的发展，还能为其它领域的发展提供有力的工具，是图谱理论研究的热点问题。.本项目将研究基于Laplace矩阵、正规化Laplace矩阵的图结构和图参数，包括以下内容：(1)通过研究Laplace矩阵和正规化Laplace矩阵，得到一些重要图类的基尔霍夫指数、度积-基尔霍夫指数以及生成树数目等参数的表达式；(2)研究hitting time期望值、覆盖成本和反覆盖成本的极值问题；(3)研究随机符号图的能量和Laplace能量。本项目的研究将拓展图谱理论、极值图论和随机图论研究的内涵，进一步推动我国代数图论与组合矩阵论的研究水平。

图的Laplace矩阵和正规化Laplace矩阵与图的一些参数比如hitting time期望值、电阻距离、基尔霍夫指数、度积-基尔霍夫指数、生成树数目以及Laplace能量等都密切相关。研究这些参数与图结构的联系不仅能大力促进图谱理论的发展，还能为其它领域的发展提供有力的工具，是图谱理论研究的热点问题。.本项目主要研究了基于Laplace矩阵、正规化Laplace矩阵的图结构和图参数，主要研究结果如下：.(1)通过Laplace多项式的分解定理以及特征多项式的根与系数的关系，确定了两类特殊的化学图的基尔霍夫指数和生成树数目的公式；(2)刻画了给定片段序列的树、k-叉树以及哑铃图等图类中，覆盖时间(或反覆盖时间)取得极值（极大或极小）时候的极值图；(3)研究了随机符号图和随机二部符号图的能量刻画问题，并确定了随机多部符号图的上下界。