کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4653298 1632763 2016 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Relation between the skew-rank of an oriented graph and the rank of its underlying graph
ترجمه فارسی عنوان
رابطه بین رتبه تقریبی یک گراف گرا و رتبه گرافیکی زیرین آن
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 54, May 2016, Pages 76–86
نویسندگان
, , ,