Skew-rank of an oriented graph in terms of matching number

详细信息    查看全文

• 作者：Xiaobin Ma^a ; ¹ ; Dein Wong^b ; ² ; ^{wongdein@163.com" class="auth_mail" title="E-mail the corresponding author} ; Fenglei Tian^b
• 关键词：05C20 ; 05C50 ; 05C75
• 刊名：Linear Algebra and its Applications
• 出版年：2016
• 出版时间：15 April 2016
• 年：2016
• 卷：495
• 期：Complete
• 页码：242-255
• 全文大小：359 K

文摘

An oriented graph G^σ$G^{\sigma }$ is a digraph without loops and multiple arcs, where G   is called the underlying graph of G^σ$G^{\sigma }$. Let S(G^σ)$S(G^{\sigma })$ denote the skew-adjacency matrix of G^σ$G^{\sigma }$. The rank of S(G^σ)$S(G^{\sigma })$ is called the skew-rank of G^σ$G^{\sigma }$, denoted by sr(G^σ)$\mathit{sr}(G^{\sigma })$, which is even since S(G^σ)$S(G^{\sigma })$ is skew symmetric. Li and Yu (2015) [12] proved that the skew-rank of an oriented unicyclic graph G^σ$G^{\sigma }$ is either 2m(G)−2$2m(G)-2$ or 2m(G)$2m(G)$, where m(G)$m(G)$ denotes the matching number of G  . In this paper, we extend this result to general cases. It is proved that the skew-rank of an oriented connected graph G^σ$G^{\sigma }$ is an even integer satisfying c702e3d383cd5996735ace3" title="Click to view the MathML source">2m(G)−2β(G)≤sr(G^σ)≤2m(G)$2m(G)-2\beta (G)\le \mathit{sr}(G^{\sigma })\le 2m(G)$, where β(G)=|E(G)|−|V(G)|+1$\beta (G)=|E(G)|-|V(G)|+1$ is the number of fundamental cycles (also called the first Betti number). Besides, the oriented graphs satisfying sr(G^σ)=2m(G)−2β(G)$\mathit{sr}(G^{\sigma })=2m(G)-2\beta (G)$ are characterized definitely.