Oriented graphs determined by their generalized skew spectrum
Oriented graphs determined by their generalized skew spectrum
复制标题
DOI：
10.1016/j.laa.2021.03.033
复制
发表时间：
2021-03
影响因子：
1.1
通讯作者：
Lihong Qiu;Wen Wang;Wei Wang
中科院分区：
文献类型：
--
作者：
Lihong Qiu;Wen Wang;Wei Wang
图的谱刻画是谱图理论中的一个重要研究课题，受到了很多研究者的关注。然而，定向图的谱特征迄今为止研究得较少。给定一个简单无向图G，G具有方向σ，有向图G σ是由G的每条边按σ赋予方向而得到的有向图。一个有向图G σ是自逆的，如果它与它的匡威（G σ）T同构，逆（G σ）T是由G σ通过反转G σ中的每个有向边而得到的图。我们用S（G σ）表示G σ的斜邻接矩阵。对于分别具有斜邻接矩阵S（G σ）和S（H τ）的两个定向图G σ和H τ，如果对任意t∈ R，两个矩阵tJ − S（G σ）和tJ − S（H τ）具有相同的谱，则称G σ是H τ的R-共谱，其中J是全一矩阵.一个有向图G σ称为由广义斜谱（DGSS）决定的，如果任何与G σ R-共谱的有向图都同构于G σ. DGSS的有向图必须是自逆的。本文给出了自逆定向图是DGSS的一个简单的算术条件，它提供了一个类似于普通图的类似结果，见[15]。更精确地说，设G σ是一个具有斜邻接矩阵S（G σ）的自逆定向图，W（G σ）=[e，S（G σ）e，n，Sn − 1（G σ）e]（e是全一向量）是斜行走矩阵。我们证明了如果2− <$n 2 det <$W（G σ）是奇的且无平方的，则G σ是DGSS。此外，我们还说明了我们的结果在一定意义下是最好的。
Spectral characterization of graphs is a well-studied topic in spectral graph theory which has received a lot of attention from researchers. The spectral characterization of oriented graphs, however, is less studied so far. Given a simple undirected graph G with an orientation σ, the oriented graph G σ is a digraph obtained from G by assigning to every edge of G a direction according to σ. An oriented graph G σ is self-converse if it is isomorphic to its converse (G σ) T, a graph obtained from G σ by reversing each directed edge in G σ. We denote by S (G σ) the skew-adjacency matrix of G σ. For two oriented graphs G σ and H τ with skew-adjacency matrices S (G σ) and S (H τ), respectively, we say G σ is R-cospectral to H τ, if for any t∈ R, two matrices t J− S (G σ) and t J− S (H τ) have the same spectrum, where J is the all-one matrix. An oriented graph G σ is said to be determined by the generalized skew spectrum (DGSS for short) if, any oriented graph R-cospectral to G σ is isomorphic to G σ. Oriented graphs that are DGSS must be self-converse. In this paper, we give a simple arithmetic condition for a self-converse oriented graph being DGSS, which provides an analogue of a similar result for ordinary graphs; see [15]. More precisely, let G σ be a self-converse oriented graph with skew-adjacency matrix S (G σ), and W (G σ)=[e, S (G σ) e,⋯, S n− 1 (G σ) e](e is the all-one vector) be the skew-walk-matrix. We show that if 2−⌊ n 2⌋ det W (G σ) is odd and square-free, then G σ is DGSS. Moreover, we also illustrate that our result is the best possible in certain sense.