Laplacian Energy of Digraphs and a Minimum Laplacian Energy Algorithm
Laplacian Energy of Digraphs and a Minimum Laplacian Energy Algorithm
复制标题
DOI：
10.1142/s0129054115500203
复制
发表时间：
2015-07
期刊：
影响因子：
--
通讯作者：
Xingqin Qi;Edgar Fuller;Rong Luo;G. Guo;Cun-Quan Zhang
中科院分区：
文献类型：
--
作者：
Xingqin Qi;Edgar Fuller;Rong Luo;G. Guo;Cun-Quan Zhang
在谱图理论中，无向图的拉普拉斯能量得到了广泛的研究。然而，对于有向图的研究还很少。最近，Perera和Mizoguchi（2010）引入了有向拉普拉斯矩阵L=D−A和有向拉普拉斯能量LE（G）=∑i=1nλi2，对于n个顶点的有向图G，使用L的二阶谱矩，其中D是对角出度矩阵，A=（aij），当从顶点i到顶点j有弧（i，j）时，aij=1，否则为0。他们研究了两类特殊有向图（简单有向图和对称有向图）的有向拉普拉斯能量。本文推广了既允许简单弧又允许对称弧的有向图的拉普拉斯能量的研究。我们提出了这样的有向图的拉普拉斯能量的上下界，并刻画了达到上下界的极值图。我们还提出了一个多项式算法，以找到一个简单的无向图的最佳方向，使所得到的有向图具有最小的拉普拉斯能量在所有方向。这解决了Perera和Mizoguchi在2010年提出的一个开放问题。
In spectral graph theory, the Laplacian energy of undirected graphs has been studied extensively. However, there has been little work yet for digraphs. Recently, Perera and Mizoguchi (2010) introduced the directed Laplacian matrix L=D−A and directed Laplacian energy LE(G)=∑i=1nλi2 using the second spectral moment of L for a digraph G with n vertices, where D is the diagonal out-degree matrix, and A=(aij) with aij=1 whenever there is an arc (i,j ) from the vertex i to the vertex j and 0 otherwise. They studied the directed Laplacian energies of two special families of digraphs (simple digraphs and symmetric digraphs). In this paper, we extend the study of Laplacian energy for digraphs which allow both simple and symmetric arcs. We present lower and upper bounds for the Laplacian energy for such digraphs and also characterize the extremal graphs that attain the lower and upper bounds. We also present a polynomial algorithm to find an optimal orientation of a simple undirected graph such that the resulting oriented graph has the minimum Laplacian energy among all orientations. This solves an open problem proposed by Perera and Mizoguchi at 2010.