簡單圖的秩、定向圖的斜秩與圍長的關系

劉夢,王龍

摘要：給出簡單圖的秩和定向圖的斜秩與圍長的關系，論證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.

編輯：琳莉