刘梦,王龙

摘要：给出简单图的秩和定向图的斜秩与围长的关系，论证r（G）=g（G）-2，sr（Gσ）=g（G）-2时的充分必要条件.

关键词：秩;围长;斜秩;定向图

[中图分类号]O157.6[文献标志码]A

The Relation between Rank and Girth of Simple Graph and the

Relation between Skewrank and Girth of Directional Graph

LIU Meng，WANG Long

（Anhui University of Science and Technology，Huainan 232001，China）

Abstract：The relations between the rank of simple graphs and the skewrank of directional graphs and the circumference length are given，and the sufficient and necessary conditions of r（G）=g（G）-2，sr（Gσ）=g（G）-2are proved.

Key words：rank;girth;kewrank;directed graph

圈图的围长和定向图的斜邻接矩阵是许多学者研究的焦点.Juan Monsalve[1]等解决了定向图的斜能量问题.徐礼礼[2]研究了一个路与一个完全二部图直积标号的问题.Adiga[3]描述了多种图的斜能量知识.赵炳荧[4]等描述了构造等斜能量定向图的两种方法.李学良和于桂海[5]研究了定向图的斜秩问题，刻画了围长为k的n阶单圈定向图的斜秩.岳靖[6]等对秩为1的某些特殊矩阵进行研究，给出了n阶特殊矩阵的相关问题.Guo[7]等人研究了具有小围长平面图的强边染色的问题.Li jing[8]刻画了无偶圈有向图的极值斜能量的问题.本文给出简单图的秩和定向图的斜秩与围长的关系，论证r（G）=g（G）-2，sr（Gσ）=g（G）-2时的充分必要条件.

1相关引理

记G=V（G），E（G）是一个点集，边集分别为V（G）={v1，v2，…，vn}，E（G）的n阶连通图.图G的邻接矩阵记为A（G）=（aij）n×n.如果vi和vj相邻，则aij=1;否則，aij=0.邻接矩阵A（G）的秩为图G的秩，记为r（G）.在图G的基础上，当G中的每一条边都给予方向时，就会得到一个定向图，记为Gσ，G称为Gσ的底图.记（uv）为Gσ由u指向v的一条弧.定向图Gσ的斜邻接矩阵记为S（Gσ），定义为一个n×n阶反对称矩阵[sxv]，如果存在一条从x到y的弧，则

sxv=-svx=1;否则，sxv=0.Gσ的斜秩记为sr（Gσ），定义为斜邻接矩阵S（Gσ）的秩.sr（Gσ）总是偶数，因为邻接矩阵S（Gσ）是反对称的.设Cσn=v1v2v3，vnv1是一个具有偶数个顶点的定向圈，Cσn的符号sgn（Cσn）定义为∏ni=1svivi+1的符号，其中vn+1=v1，如果偶定向圈Cσn的符号是正的，则称Cσn是偶定向的;如果是负的，则是奇定向的.G的围长g（G）定义为图G中最短圈的长度.由图G顶点的一个子集和图G中两端均在该子集的所有的边的集合组成的图，称为G的导出子图.Cn为n个顶点的圈.

引理1[914]对于Cn，有

r（Cn）=n，如n≠0（mod 4）

n-2，如n=0（mod 4）.

引理2[9]设H是图G的一个诱导子图，则有

r（H）≤r（G）.

引理3[10]r（G）=2，当且仅当G为完全二部图Km.n（m.n≥1）.

引理4[3]连通路Pk的秩，有

r（Pk）=k，k为偶数

k-1，k为奇数.

引理5[11]设y是图G的悬挂点，x是图G中与y相邻的拟悬挂点，则

r（G）=r（G-x-y）+2.

引理6[12]设Hσ是Gσ的一个诱导子图，则有

sr（Hσ）≤sr（Gσ）.

引理7[12]Cσn是具有n个顶点的定向圈，则

sr（Cσn）==n，如果Cσn是奇定向

=n-2，如果Cσn是偶定向

=n-1，其他.

引理8[12]设Pσn为一个具有n个顶点的定向路，则

sr（Pσn）=n-1，n为奇数

n，n为偶数.

引理9[1213]设Gσ是一个定向图，v是Gσ的一个悬挂点，u是v的唯一邻接点，则

sr（Gσ）=sr（Gσ-u-v）+2.

引理10[15]Gσ是一个斜秩为2的n阶（n=2，3，4）连通定向图，以下情况成立：

（1）如果n=2，Gσ是任意方向的一个定向路Pσ2.

（2）如果n=3，当Gσ中每一条边都有方向，Gσ是Kσ3或Pσ3.

（3）如果n=4，那么Gσ是以下几种形式的定向图之一：a.偶定向圈Cσ4;b.每条边都有任意方向的Kσ1.3;c.偶定向图Kσ1，1，2.

引理11[15]Gσ是任是一个n阶，其中n≥5的连通定向图，sr（Gσ）=2，当且仅当Gσ的底图是完全二部图或三部图并且Gσ中的Cσ4都是偶定向的.

2主要结果

包含圈的连通图G可以计算出秩和围长，笔者根据连通图G和Gσ的秩和围长及各自导出子图的秩和围长来确定秩与围长的关系，分别为r（G）≥g（G）-2和sr（Gσ）≥g（G）-2，并给出了r（G）=g（G）-2和sr（Gσ）=g（G）-2的充分必要条件.

定理1设G是一个带圈的连通图，则r（G）≥g（G）-2.进一步，r（G）=g（G）-2当且仅当G为Ckk≥8且k=0（mod 4）或G为完全二部图Km，l.

证明记g（G）=g，由围长的定义可知，Cg为G的导出子图.

根据引理2，可得r（Cg）≤r（G）.

根据引理1，可得r（Cg）≥g-2.

综上所述，可得r（G）≥r（Cg）≥g-2.

因此r（G）≥g（G）-2.

证明定理1中r（G）=g（G）-2的充分必要条件.

充分性证明（1）当G为Ckk≥8且k=0（mod 4）时，根据引理1不难看出r（G）=g（G）-2.

（2）G为完全二部图km，l时，根据引理3可知，r（G）=2，g（G）=4，所以，r（G）=g（G）-2.

由（1）（2）可知，当G为Ckk≥8且k=0（mod 4）或G为完全二部图km，l时，r（G）=g（G）-2.

必要性证明设Cg为G的导出子图，由不等式r（G）≥g（G）-2的证明可知，r（G）=g（G）-2时，r（Cg）=g（G）-2，根据引理1可知，Cg中g=0（mod 4）.

（1）g≥8时，运用反证法.如果G≠Cgg≥8（mod 4）时，则Cg外必存在一点x满足x∈V（G）但x∈/V（Cg），且NCg（x）≠0.由于g（G）=g，则NCg（x）=1，记NCg（x）={y}.设图H由图G中Cg与点y导出，根据引理2可得r（H）≤r（G），且Cg是H的导出子图，则有

g-2≤r（H）≤r（G）.

删除H中点x与点y得到的图记为I，根据引理5，可得r（I）=r（H）-2.

根据引理4，可得r（I）=g-2.

则有r（H）=g.

又因为r（H）≤r（G），可以得出r（G）≥g.

此时r（G）≥g与r（G）=g-2相矛盾，反证不成立，所以当r（G）=g（G）-2且g≥8时，G=Cgg≥8（mod 4）.

（2）当g=4，则r（G）=2，根据引理3可知G=Km，l.

由（1）（2）可知，当r（G）=g（G）-2时，G只能为Ckk≥8且k=0（mod 4）或完全二部图Km，l.

综上所述，r（G）=g（G）-2当且仅当G为Ckk≥8且k=0（mod 4）或G为完全二部图Km，l.

定理2G是一个带圈的连通图，当每条边给予方向后，成为一个带圈的定向图Gσ，则sr（Gσ）≥g（G）-2.进一步，sr（Gσ）=g（G）-2当且仅当Gσ为Cσkk=0（mod 4）且Cσk为偶定向或Gσ为完全二部图Km，l（每一个4圈都是偶定向的）.

证明记g（Gσ）=g，由围长的定义可知，Cσg为Gσ的导出子图.

根据引理6，可得sr（Cσg）≤sr（Gσ）.

根据引理7，可得

sr（Cσg）min=g（G）-2.sr（Cσg）≥g（G）-2.

综上所述，可得

sr（Gσ）≥sr（Cσg）≥g（G）-2.

因此sr（Gσ）≥g（G）-2.

证明定理2中sr（Gσ）=g（G）-2的充分必要条件.

充分性证明 （1）当Gσ为Cσkk=0（mod 4）且Cσk為偶定向时，根据引理1和引理7不难看出sr（Cσg）min=g（G）-2.

（2）当Gσ为完全二部图Km，l（每一个4圈都是偶定向的）时，根据引理10和引理11可知，sr（Kσm，l）=2，g（Kσm，l）=4，所以，sr（Kσm，l）=g（Kσm，l）-2.

由（1）（2）可知，当Gσ为Cσkk≥8，k=0（mod 4）且Cσk为偶定向或Gσ为完全二部图Km，l（每一个4圈都是偶定向的）时，sr（Cσk）=g（G）-2.

必要性证明设Cσg为Gσ的导出子图，由不等式sr（Gσ）≥g（G）-2的证明可知，sr（Gσ）=g（G）-2时，sr（Cσg）=g（G）-2，根据引理1和引理7可知，Cσg中g=0（mod 4）且Cσg是偶定向的.

（1）当g≥8且Cσg是偶定向时，运用反证法.

如果Gσ≠Cσgg≥8，g=0（mod 4）且Cσg是偶定向的时，则Cσg外必存在一点x满足x∈V（Gσ）但x∈/V（Cσg）且NCσk（x）≠0.由于g（Gσ）=g，则NCσk（x）=1，设NCσk（y）={y}.图H由图Cσg与点y导出，根据引理6可得sr（H）≤sr（G），且Cσg是H的导出子图，则有

g-2≤sr（H）≤sr（G）.

删除H中点x与点y得到的图记为I，根据引理9，可得sr（I）=sr（H）-2.

根据引理8，可得sr（I）=g-2.

则有sr（H）=g.

又因为sr（H）≤sr（Gσ），可以得出sr（Gσ）≥g，

此时sr（Gσ）≥g与sr（Gσ）=g-2相矛盾，反证不成立，所以当sr（Cσg）=g（G）-2且g≥8时，Gσ=Cσkk≥8，k=0（mod 4）且Cσk为偶定向.

（2）当g=4时，则sr（Gσ）=2，根据引理10和引理11有以下几种情况：a.偶定向圈Cσ4;b.每条边都有任意方向的Kσ1，3;c.偶定向图Kσ1，1，2;d.Gσ为Cσgg≥5，sr（Gσ）=2，当且仅当Gσ的底图是完全二部图或三部图且Gσ中Cσ4都是偶定向的.因为本文考虑带圈的连通定向图，所以只有a和d这两种情况符合.

由（1）（2）可知，当sr（Gσ）=g（G）-2，Cσk=Cσ4或Gσ=Km，l（每一个4圈都是偶定向的）.

综上所述，sr（Gσ）=g（G）-2当且仅当Gσ为Cσkk=0（mod 4），且Cσk为偶定向或Gσ为完全二部图Km，l（每一个4圈都是偶定向的）.

参考文献

[1]Juan Monsalve，Juan Rada.Oriented bipartite graphs with minimal trace norm[J].Linear and Multilinear Algebra，2019，67（6） ：11211131.

[2]徐礼礼，董晓媛，马登举.一个路与一个完全二部图直积的L（2，1）标号[J].牡丹江师范学院学报：自然科学版，2016（2）：78.

[3]C. Adiga，R. Balakrishnan，Wasin So.The skew energy of a digraph[J].Linear Algebra and its Applications，2010，432（7）：18251835.

[4]赵炳荧，冀孟达，王盟.构造等斜能量定向图的两种方法[J].华中师范大学学报：自然科学版，2021，55（4）：507511.

[5]李学良，于桂海.定向图的斜秩[J].中国科学：数学，2015，45（1）：93104.

[6]岳靖，朱建鹏.秩为1的n阶特殊矩阵相关问题解法探讨[J].牡丹江师范学院学报：自然科学版，2015（4）：810.

[7]Guo Yirong，Zhang Xia，Zhang Xinmiao.Strong edgecolorings of planar graphs with small girth[J].Applied Mathematics and Computation，2021，394：179196.

[8]Jing Li，Xueliang Li，Huishu Lian.Extremal skew energy of digraphs with no even cycles[J].Transactions on Combinatorics，2014，3（1）：3749.

[9]Bo Cheng，Muhuo Liu，Bolian Liu.Proof of a conjecture on the nullity of a connected graph in terms of order and maximum degree[J].Linear Algebra and Its Applications，2020， 587：291301.

[10]Xueliang Li，Guihai Yu.The skewrank of oriented graphs[J].Scientia Sinica：Mathematica，2015：93104.

[11]Bo Cheng，Muhuo Liu，Bolian Liu.Proof of a conjecture on the nullity of a connected graph in terms of order and maximum degree[J].Linear Algebra and Its Applications，2020，587：291301.

[12]盧勇，王力工，孔琪.一些定向图的斜秩[J].应用数学，2017，30（1）：105111.

[13]Hong Zhen Mu，Xia Zheng Jiang，Lai Hong Jian，Liu Ruifang.Fractional arboricity，strength and eigenvalues of graphs with fixed girth or clique number[J].Linear Algebra and its Applications，2020：5166.

[14]Shengbiao Hu，Tan Xuezhong，Bolian Liu. On the nullity of bicyclic graphs[J].Linear Algebra and Its Applications，2007，429（7） ：13871391.

[15]D.Cvetkovi，M.Doob，H.Spectra of Graphs，third ed[M].Johann Ambrosius Barth，Heidelberg，1995.

编辑：琳莉