运算图的各类谱及其在量子计算理论中的应用

All kinds of spectrum of graph operations have a center position in graph spectra. It has extensive applications in disciplines of complex network, computer science, quantum computing theory etc. In this project, beginning with the study of structural properties of graph operations, we shall investigate some spectra problems of graph operations and some applications in quantum computing theory. We shall try to compute all kinds of spectra of core-satellite graphs, some variants of join graphs, the vertex neighbourhood corona and edge neighbourhood corona based on total graphs in terms of the spectra of the original graphs. These results are used to construct many pairs of nonisomorphic cospectral graphs, (signless) Laplacian cospectral graphs. We shall study some properties of Q-generating function of graphs, which shall be used to study signless Laplacian spectrum of graphs. In addition, we also present some combinatorial properties of Q-coronal of graphs and compute the Q-coronals of some graph operations. Applying some structural properties of the generalized (edge) coronas and join graphs, we shall give their spectral decompositions. Furthermore, we shall obtain some sufficient conditions of perfect state transfer and pretty good state transfer in graph operations.

运算图的各类谱在图谱研究中非常重要，在复杂网络、计算机科学、量子计算理论等领域应用广泛。本项目从图的结构入手，研究运算图的各类谱及其在量子计算中的应用。对于Core-satellite图、联图的四种变异类、基于全图的点邻接冠图和边邻接冠图，刻画出其各类谱与其子图的对应谱之间的关系，从而构造出非同构的同谱图、Laplacian同谱图和无符号Laplacian同谱图类，并计算这些图类的生成树。研究图的Q-生成函数的基本性质和图的Q-coronal的组合性质，并利用其性质研究图的无符号Laplacian谱问题和讨论一些运算图的Q-coronal的计算方法。结合冠图、边冠图和广义联图的结构给出它们的谱分解表达式，进而给出它们在量子信息传递中存在完美状态迁移或者非常好的状态迁移的充分条件。

本项目围绕运算图的各类谱及其在量子信息传递中的应用等相关问题开展研究。首先，刻画了广义Core-satellite图的无符号Laplacian谱并构造出了无符号Laplacian整谱图，推广了现有结果；确定了图的S-边点联图的邻接谱、Laplacian谱和规范化Laplacian谱以及该图的生成树数目，构造出了邻接、Laplacian和规范化Laplacian同时同谱的非正则图类，部分回答了Butler提出的问题。其次，通过研究冠图和Q-图的无符号Laplacian谱分解式，给出了两类图具有完美状态迁移或非常好状态迁移的条件，利用所得结果得到了一些距离正则图的冠图和Q-图不具有完美状态迁移，但却具有非常好状态迁移的结论。再次，引入图的Q-生成函数的概念并讨论其基本性质，建立了图的Q-生成函数和图的无符号Laplacian谱之间的联系，给出了图的Q-coronal的组合性质并得到了一些运算图Q-coronal精确表达式。比较系统地建立了图的半边路、图的Q-生成函数和一些运算图的无符号Laplacian多项式之间的关系。得到了图的算术几何指标、算术几何谱半径和能量的上下界；给出了运算图如R-图、Q-图和线图的类Laplacian能量LEL和关联能量IE的上下界，结果改进和推广了现有结论。最后，引入了图的广义距离矩阵的概念并研究了其基本性质和谱半径的界，刻画了运算图如联图，双图，笛卡尔积图，双星图等的广义距离谱。证明了对于一些特殊的完全多部图和三部Turán图，当删除任意一条边时，其距离能量必增加，部分解决了Varghese等人提出的距离能量改变猜想；刻画了在禁用4-圈或5-圈的连通图中具有最大α-谱半径的图类，部分回答了Nikiforov提出的一个有关图的广义谱极值的开放问题。