Relation between the skew-rank of an oriented graph and the rank of its underlying graph
Relation between the skew-rank of an oriented graph and the rank of its underlying graph
复制标题
DOI：
10.1016/j.ejc.2015.12.005
复制
发表时间：
2016-05
期刊：
影响因子：
--
通讯作者：
Dein Wong;Xiaobin Ma;Fenglei Tian
中科院分区：
文献类型：
--
作者：
Dein Wong;Xiaobin Ma;Fenglei Tian
定向图G σ是一个不含圈和重弧的有向图，这里G称为G σ的底层图.设S（G σ）表示G σ的斜邻接矩阵，A（G）表示G的邻接矩阵. G σ的斜秩记为sr（G σ），指的是S（G σ）的秩，由于S（G σ）是斜对称的，所以S（G σ）的秩总是偶数。一个很自然的问题是：有向图G σ的斜秩与其基础图的秩之间的关系如何？在本文中，我们集中注意力在这个问题上。用d（G）表示G的循环空间的维数，即d（G）=| E（G）|−| V（G）|+ θ（G），其中θ（G）表示G的连通分支数.证明了对定向图G σ，sr（G σ）≤ r（G）+2d（G），刻画了斜秩达到上界的定向图G σ.
An oriented graph G σ is a digraph without loops and multiple arcs, where G is called the underlying graph of G σ. Let S (G σ) denote the skew-adjacency matrix of G σ, and A (G) be the adjacency matrix of G. The skew-rank of G σ, written as s r (G σ), refers to the rank of S (G σ), which is always even since S (G σ) is skew symmetric. A natural problem is: How about the relation between the skew-rank of an oriented graph G σ and the rank of its underlying graph? In this paper, we focus our attention on this problem. Denote by d (G) the dimension of cycle spaces of G, that is d (G)=| E (G)|−| V (G)|+ θ (G), where θ (G) denotes the number of connected components of G. It is proved that s r (G σ)≤ r (G)+ 2 d (G) for an oriented graph G σ, the oriented graphs G σ whose skew-rank attains the upper bound are characterized.