Article ID Journal Published Year Pages File Type
4653298 European Journal of Combinatorics 2016 11 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,