کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4653298 | 1632763 | 2016 | 11 صفحه PDF | دانلود رایگان |
An oriented graph GσGσ is a digraph without loops and multiple arcs, where GG is called the underlying graph of GσGσ. Let S(Gσ)S(Gσ) denote the skew-adjacency matrix of GσGσ, and A(G)A(G) be the adjacency matrix of GG. The skew-rank of GσGσ, written as sr(Gσ)sr(Gσ), refers to the rank of S(Gσ)S(Gσ), which is always even since S(Gσ)S(Gσ) is skew symmetric.A natural problem is: How about the relation between the skew-rank of an oriented graphGσGσand the rank of its underlying graph? In this paper, we focus our attention on this problem. Denote by d(G)d(G) the dimension of cycle spaces of GG, that is d(G)=|E(G)|−|V(G)|+θ(G)d(G)=|E(G)|−|V(G)|+θ(G), where θ(G)θ(G) denotes the number of connected components of GG. It is proved that sr(Gσ)≤r(G)+2d(G)sr(Gσ)≤r(G)+2d(G) for an oriented graph GσGσ, the oriented graphs GσGσ whose skew-rank attains the upper bound are characterized.
Journal: European Journal of Combinatorics - Volume 54, May 2016, Pages 76–86