簡單圖的秩、定向圖的斜秩與圍長的關(guān)系

劉夢,王龍

摘要：給出簡單圖的秩和定向圖的斜秩與圍長的關(guān)系，論證r（G）=g（G）-2，sr（Gσ）=g（G）-2時的充分必要條件.

關(guān)鍵詞：秩;圍長;斜秩;定向圖

[中圖分類號]O157.6[文獻(xiàn)標(biāo)志碼]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

圈圖的圍長和定向圖的斜鄰接矩陣是許多學(xué)者研究的焦點(diǎn).Juan Monsalve[1]等解決了定向圖的斜能量問題.徐禮禮[2]研究了一個路與一個完全二部圖直積標(biāo)號的問題.Adiga[3]描述了多種圖的斜能量知識.趙炳熒[4]等描述了構(gòu)造等斜能量定向圖的兩種方法.李學(xué)良和于桂海[5]研究了定向圖的斜秩問題，刻畫了圍長為k的n階單圈定向圖的斜秩.岳靖[6]等對秩為1的某些特殊矩陣進(jìn)行研究，給出了n階特殊矩陣的相關(guān)問題.Guo[7]等人研究了具有小圍長平面圖的強(qiáng)邊染色的問題.Li jing[8]刻畫了無偶圈有向圖的極值斜能量的問題.本文給出簡單圖的秩和定向圖的斜秩與圍長的關(guān)系，論證r（G）=g（G）-2，sr（Gσ）=g（G）-2時的充分必要條件.

1相關(guān)引理

記G=V（G），E（G）是一個點(diǎn)集，邊集分別為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的基礎(chǔ)上，當(dāng)G中的每一條邊都給予方向時，就會得到一個定向圖，記為Gσ，G稱為Gσ的底圖.記（uv）為Gσ由u指向v的一條弧.定向圖Gσ的斜鄰接矩陣記為S（Gσ），定義為一個n×n階反對稱矩陣[sxv]，如果存在一條從x到y(tǒng)的弧，則

sxv=-svx=1;否則，sxv=0.Gσ的斜秩記為sr（Gσ），定義為斜鄰接矩陣S（Gσ）的秩.sr（Gσ）總是偶數(shù)，因?yàn)猷徑泳仃嘢（Gσ）是反對稱的.設(shè)Cσn=v1v2v3，vnv1是一個具有偶數(shù)個頂點(diǎn)的定向圈，Cσn的符號sgn（Cσn）定義為∏ni=1svivi+1的符號，其中vn+1=v1，如果偶定向圈Cσn的符號是正的，則稱Cσn是偶定向的;如果是負(fù)的，則是奇定向的.G的圍長g（G）定義為圖G中最短圈的長度.由圖G頂點(diǎn)的一個子集和圖G中兩端均在該子集的所有的邊的集合組成的圖，稱為G的導(dǎo)出子圖.Cn為n個頂點(diǎn)的圈.

引理1[914]對于Cn，有

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

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

引理2[9]設(shè)H是圖G的一個誘導(dǎo)子圖，則有

r（H）≤r（G）.

引理3[10]r（G）=2，當(dāng)且僅當(dāng)G為完全二部圖Km.n（m.n≥1）.

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

r（Pk）=k，k為偶數(shù)

k-1，k為奇數(shù).

引理5[11]設(shè)y是圖G的懸掛點(diǎn)，x是圖G中與y相鄰的擬懸掛點(diǎn)，則

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

引理6[12]設(shè)Hσ是Gσ的一個誘導(dǎo)子圖，則有

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

引理7[12]Cσn是具有n個頂點(diǎn)的定向圈，則

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

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

=n-1，其他.

引理8[12]設(shè)Pσn為一個具有n個頂點(diǎn)的定向路，則

sr（Pσn）=n-1，n為奇數(shù)

n，n為偶數(shù).

引理9[1213]設(shè)Gσ是一個定向圖，v是Gσ的一個懸掛點(diǎn)，u是v的唯一鄰接點(diǎn)，則

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，當(dāng)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，當(dāng)且僅當(dāng)Gσ的底圖是完全二部圖或三部圖并且Gσ中的Cσ4都是偶定向的.

2主要結(jié)果

包含圈的連通圖G可以計算出秩和圍長，筆者根據(jù)連通圖G和Gσ的秩和圍長及各自導(dǎo)出子圖的秩和圍長來確定秩與圍長的關(guān)系，分別為r（G）≥g（G）-2和sr（Gσ）≥g（G）-2，并給出了r（G）=g（G）-2和sr（Gσ）=g（G）-2的充分必要條件.

定理1設(shè)G是一個帶圈的連通圖，則r（G）≥g（G）-2.進(jìn)一步，r（G）=g（G）-2當(dāng)且僅當(dāng)G為Ckk≥8且k=0（mod 4）或G為完全二部圖Km，l.

證明記g（G）=g，由圍長的定義可知，Cg為G的導(dǎo)出子圖.

根據(jù)引理2，可得r（Cg）≤r（G）.

根據(jù)引理1，可得r（Cg）≥g-2.

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

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

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

充分性證明（1）當(dāng)G為Ckk≥8且k=0（mod 4）時，根據(jù)引理1不難看出r（G）=g（G）-2.

（2）G為完全二部圖km，l時，根據(jù)引理3可知，r（G）=2，g（G）=4，所以，r（G）=g（G）-2.

由（1）（2）可知，當(dāng)G為Ckk≥8且k=0（mod 4）或G為完全二部圖km，l時，r（G）=g（G）-2.

必要性證明設(shè)Cg為G的導(dǎo)出子圖，由不等式r（G）≥g（G）-2的證明可知，r（G）=g（G）-2時，r（Cg）=g（G）-2，根據(jù)引理1可知，Cg中g(shù)=0（mod 4）.

（1）g≥8時，運(yùn)用反證法.如果G≠Cgg≥8（mod 4）時，則Cg外必存在一點(diǎn)x滿足x∈V（G）但x∈/V（Cg），且NCg（x）≠0.由于g（G）=g，則NCg（x）=1，記NCg（x）={y}.設(shè)圖H由圖G中Cg與點(diǎn)y導(dǎo)出，根據(jù)引理2可得r（H）≤r（G），且Cg是H的導(dǎo)出子圖，則有

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

刪除H中點(diǎn)x與點(diǎn)y得到的圖記為I，根據(jù)引理5，可得r（I）=r（H）-2.

根據(jù)引理4，可得r（I）=g-2.

則有r（H）=g.

又因?yàn)閞（H）≤r（G），可以得出r（G）≥g.

此時r（G）≥g與r（G）=g-2相矛盾，反證不成立，所以當(dāng)r（G）=g（G）-2且g≥8時，G=Cgg≥8（mod 4）.

（2）當(dāng)g=4，則r（G）=2，根據(jù)引理3可知G=Km，l.

由（1）（2）可知，當(dāng)r（G）=g（G）-2時，G只能為Ckk≥8且k=0（mod 4）或完全二部圖Km，l.

綜上所述，r（G）=g（G）-2當(dāng)且僅當(dāng)G為Ckk≥8且k=0（mod 4）或G為完全二部圖Km，l.

定理2G是一個帶圈的連通圖，當(dāng)每條邊給予方向后，成為一個帶圈的定向圖Gσ，則sr（Gσ）≥g（G）-2.進(jìn)一步，sr（Gσ）=g（G）-2當(dāng)且僅當(dāng)Gσ為Cσkk=0（mod 4）且Cσk為偶定向或Gσ為完全二部圖Km，l（每一個4圈都是偶定向的）.

證明記g（Gσ）=g，由圍長的定義可知，Cσg為Gσ的導(dǎo)出子圖.

根據(jù)引理6，可得sr（Cσg）≤sr（Gσ）.

根據(jù)引理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）當(dāng)Gσ為Cσkk=0（mod 4）且Cσk為偶定向時，根據(jù)引理1和引理7不難看出sr（Cσg）min=g（G）-2.

（2）當(dāng)Gσ為完全二部圖Km，l（每一個4圈都是偶定向的）時，根據(jù)引理10和引理11可知，sr（Kσm，l）=2，g（Kσm，l）=4，所以，sr（Kσm，l）=g（Kσm，l）-2.

由（1）（2）可知，當(dāng)Gσ為Cσkk≥8，k=0（mod 4）且Cσk為偶定向或Gσ為完全二部圖Km，l（每一個4圈都是偶定向的）時，sr（Cσk）=g（G）-2.

必要性證明設(shè)Cσg為Gσ的導(dǎo)出子圖，由不等式sr（Gσ）≥g（G）-2的證明可知，sr（Gσ）=g（G）-2時，sr（Cσg）=g（G）-2，根據(jù)引理1和引理7可知，Cσg中g(shù)=0（mod 4）且Cσg是偶定向的.

（1）當(dāng)g≥8且Cσg是偶定向時，運(yùn)用反證法.

如果Gσ≠Cσgg≥8，g=0（mod 4）且Cσg是偶定向的時，則Cσg外必存在一點(diǎn)x滿足x∈V（Gσ）但x∈/V（Cσg）且NCσk（x）≠0.由于g（Gσ）=g，則NCσk（x）=1，設(shè)NCσk（y）={y}.圖H由圖Cσg與點(diǎn)y導(dǎo)出，根據(jù)引理6可得sr（H）≤sr（G），且Cσg是H的導(dǎo)出子圖，則有

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

刪除H中點(diǎn)x與點(diǎn)y得到的圖記為I，根據(jù)引理9，可得sr（I）=sr（H）-2.

根據(jù)引理8，可得sr（I）=g-2.

則有sr（H）=g.

又因?yàn)閟r（H）≤sr（Gσ），可以得出sr（Gσ）≥g，

此時sr（Gσ）≥g與sr（Gσ）=g-2相矛盾，反證不成立，所以當(dāng)sr（Cσg）=g（G）-2且g≥8時，Gσ=Cσkk≥8，k=0（mod 4）且Cσk為偶定向.

（2）當(dāng)g=4時，則sr（Gσ）=2，根據(jù)引理10和引理11有以下幾種情況：a.偶定向圈Cσ4;b.每條邊都有任意方向的Kσ1，3;c.偶定向圖Kσ1，1，2;d.Gσ為Cσgg≥5，sr（Gσ）=2，當(dāng)且僅當(dāng)Gσ的底圖是完全二部圖或三部圖且Gσ中Cσ4都是偶定向的.因?yàn)楸疚目紤]帶圈的連通定向圖，所以只有a和d這兩種情況符合.

由（1）（2）可知，當(dāng)sr（Gσ）=g（G）-2，Cσk=Cσ4或Gσ=Km，l（每一個4圈都是偶定向的）.

綜上所述，sr（Gσ）=g（G）-2當(dāng)且僅當(dāng)Gσ為Cσkk=0（mod 4），且Cσk為偶定向或Gσ為完全二部圖Km，l（每一個4圈都是偶定向的）.

參考文獻(xiàn)

[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）標(biāo)號[J].牡丹江師范學(xué)院學(xué)報：自然科學(xué)版，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]趙炳熒，冀孟達(dá)，王盟.構(gòu)造等斜能量定向圖的兩種方法[J].華中師范大學(xué)學(xué)報：自然科學(xué)版，2021，55（4）：507511.

[5]李學(xué)良，于桂海.定向圖的斜秩[J].中國科學(xué)：數(shù)學(xué)，2015，45（1）：93104.

[6]岳靖，朱建鵬.秩為1的n階特殊矩陣相關(guān)問題解法探討[J].牡丹江師范學(xué)院學(xué)報：自然科學(xué)版，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].應(yīng)用數(shù)學(xué)，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.

編輯：琳莉