定向图的斜秩  

The skew-rank of oriented graphs

作　　者：李学良[1] 于桂海[1,2] 

机构地区：[1]南开大学组合数学研究中心,天津300071 [2]山东工商学院数学与信息科学学院,烟台264005

出　　处：《中国科学：数学》2015年第1期93-104,共12页Scientia Sinica：Mathematica

基　　金：国家自然科学基金(批准号:11301302和11371205);中国博士后基金(批准号:2013M530869和2014T70210);山东省博士基金(BS2013SF009)资助项目

摘　　要：定向图Gσ是一个不含有环(loop)和重边的有向图,其中G称作它的基图.S(Gσ)是Gσ的斜邻接矩阵.S(Gσ)的秩称为Gσ的斜秩,记为sr(Gσ).定向图的斜邻接矩阵是斜对称的,因而,它的斜秩是偶数.本文主要考虑简单定向图的斜秩,首先给出斜秩的一些简单基本知识,紧接着分别刻画斜秩是2的定向图和斜秩是4的带有悬挂点的定向图;其次利用匹配数给出具有n个顶点、围长是k的单圈图的斜秩表达式;作为推论,列出斜秩是4的所有单圈图和带有悬挂点的双圈图;另外研究具有n个顶点、围长是k的单圈图的图类中斜秩的最小值,并刻画了极图;最后研究斜邻接矩阵是非奇异的定向单圈图.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σ. The rank of the skew-adjacency matrix of Gσis called the skew-rank of Gσ, denoted by sr（Gσ）. The skew-adjacency matrix of an oriented graph is skew symmetric and the skew-rank is even. We consider the skew-rank of simple oriented graphs. Firstly, we give some preliminary results about the skew-rank. Secondly, we characterize the oriented graphs with skew-rank 2 and characterize the oriented graphs with pendant vertices which attain the skew-rank 4. As a consequence, we list the oriented unicyclic graphs, the oriented bicyclic graphs with pendant vertices which attain the skew-rank 4.Moreover, we determine the skew-rank of oriented unicyclic graphs of order n with girth k in terms of matching number. We investigate the minimum value of the skew-rank among oriented unicyclic graphs of order n with girth k and characterize oriented unicyclic graphs attaining the minimum value. In addition, we consider oriented unicyclic graphs whose skew-adjacency matrices are nonsingular.

关 键 词：定向图 斜邻接矩阵 斜秩 

分 类 号：O157.5[理学—数学]