毛毛蟲圖的r次冪的最小斜秩

沈小玲，候輝平

(湖南師范大學數(shù)學與計算機科學學院，中國 長沙 410081)

毛毛蟲圖的r次冪的最小斜秩

沈小玲*，候輝平

(湖南師范大學數(shù)學與計算機科學學院，中國 長沙 410081)

圖的最小斜秩問題是確定圖的所有斜對稱矩陣在域F上的秩的最小值.利用構造矩陣和零強迫集的方法刻畫了毛毛蟲圖的r次冪的最小斜秩.設毛毛蟲Tn有n個節(jié)點,n和r都是正整數(shù)，r是奇數(shù)，那么

最小斜秩；斜對稱矩陣；毛毛蟲圖的r次冪

設G是一個無環(huán)無重邊的簡單圖,頂點集為V(G),邊集E(G).用|G|表示G的頂點數(shù).頂點v的度數(shù)用dG(v)(或d(v))表示.度為k的頂點也叫k-頂點.度為1的頂點叫懸掛點.若樹圖中恰有一個度大于2的頂點，則這棵樹叫做似星樹.設集合S?V,由S導出的子圖記為G[S].若S僅包含一個頂點v,則用G-v代替G-S.圖G的j次冪是指圖Gj=(V,F),邊{u,v}∈F當且僅當存在u到v長為j的路.

圖1 毛毛蟲TnFig.1 Caterpillar Tn

在路的節(jié)點上加懸掛邊所得的圖就是毛毛蟲圖.在本文中，除特別說明，我們規(guī)定每條毛毛蟲至少有2個非懸掛點.這些非懸掛點稱為節(jié)點.設Tn是一顆有n個節(jié)點的毛毛蟲.一條毛毛蟲是正則的是指直徑路P中沒有兩個連續(xù)的頂點的關節(jié)，否則稱為不正則的.設毛毛蟲的節(jié)點i有mi條腳，標記為ai,1,…,ai,mi,i∈{1,…,n},如圖1所示；m1,mn≥1,mj≥0,j∈{2,3,…,n-1}.

1 預備知識

域F上的由圖G所描述的斜對稱矩陣的集合

S-(F,G)={A∈Fn×n:AT=-A；G(A)=G}.

圖G在域F上的最小斜秩(minimum skew-rank)定義為：mr-(F,G)=min{rankA:A∈S-(F,G)}.圖G在域F上最大斜零度定義為：M-(F,G)=max{null(A):A∈S-(F,G)}.顯然，mr-(F,G)+M-(F,G)=|G|.圖G的最大斜秩是指：MR-(F,G)=max{rankA:A∈S-(F,G)}.有關最小秩和斜秩的研究及背景見參考文獻[1～13].

定義1[11]設圖G=(V，E).

設Z是V的子集，若將Z中的所有點都著黑色，不在Z中的點都著白色，則稱集合Z是初始顏色集.

斜顏色改變規(guī)則是指：如果V中的頂點v恰有一個著白色的與之相鄰的頂點w,將w的顏色變成黑色.這種情況下，我們說v強迫w.

給定一個初始顏色集Z，將Z應用斜顏色改變規(guī)則對頂點改變顏色，直到V中沒有頂點的顏色可以改變，所得的最終結果叫做Z的斜導出色集.

一個斜零強迫集是指子集Z?V的導出色集是V.

斜零強迫數(shù)Z(G)是指斜零強迫集的最小元素個數(shù).

引理1[11]對任意圖G和任意域F，M-(F,G)≤Z-(G),mr-(F,G)≥|G|-Z-(G).

以下是關于匹配和最小斜秩的一些已知的結果.

引理2[11]給定圖G.

(1)域F上的任何最小斜秩都是偶數(shù).

(2)在mr-(G)和MR-(G)之間的任意偶秩都能實現(xiàn).

(3)mr-(G)=|G|當且僅當G有唯一完美匹配.

(4)MR-(G)=2match(G).

(5)如果T是一顆樹，那么mr-(T)=2match(T)=MR-(T).

(6)mr-(G)=2當且僅當G是完全多部圖.

(7)如果H是G的一個導出子圖，那么mr-(H)≤mr-(G).

引理4[12-13]設n和r是正整數(shù)，n≥3,

(1)如果r是奇數(shù)，那么

(2)如果r=2s，那么

2 主要結論

本節(jié)我們主要研究毛毛蟲的k次冪的斜對稱矩陣的最小秩.為方便，我們將斜對稱矩陣的最小秩簡稱為最小斜秩.

引理5設毛毛蟲Tn有n個節(jié)點，n和r都是正整數(shù),r≥n,那么

定理1設毛毛蟲Tn有n個節(jié)點，n和r都是正整數(shù)，r是奇數(shù)，那么

證將毛毛蟲的除了最后一個懸掛點外，其余的懸掛點都變成黑色，同時將前r-1個節(jié)點變成黑色.則這些黑點所構成的集合是毛毛蟲的零強迫集，其零強迫順序鏈為：

a1,1→r,1→r+1,…,n-r→n,n-r+1→an,mn.

證設n=2s+1,x=2t.如果Tn的前2(s-t)-1個節(jié)點的度數(shù)都不小于3，而其余節(jié)點的度數(shù)都為2(見圖3).為方便，圖中僅以2(s-t)-1個3-度頂點來代替度數(shù)都不小于3的頂點.

圖3 有2(s-t)-1個3-度節(jié)點其余節(jié)點度為2的毛毛蟲Tn及Fig.3 Caterpillar Tn and with 2(s-t)-1 3-degree vertices, the rest vertices are all of degree 2

同理可證下面定理.

當毛毛蟲Tn只有第一個節(jié)點的度大于2，即Tn為圖4中的Sm.不妨設有c個懸掛點與頂點1相鄰.我們有如下結論.

性質2對于圖Sr,r為偶數(shù)，

圖4 圖

圖5 毛毛蟲T5和它的2次冪.Fig.5 Caterpillar T5 and its 2-power

如果毛毛蟲的第一個和最后一個節(jié)點度大于2，記為圖Wm，那么

同理可證，

圖6 圖T5及

性質4對于圖Wm,當m為偶數(shù)時,

[1] BARIOLI F, BARRETT W, BUTLER S,etal. Zero forcing sets and the minimum rank of graphs[J]. Linear Algera Appl, 2008,428(7):1628-1648.

[2] BERMAN A, FRIEDLAND S, HOGBEN L,etal. An upper bound for the minimum rank of a graph[J]. Linear Algera Appl, 2008,429(7):1629-1638.

[3] BARIOLI F, FALLAT S M, HERSHKOWITZ D,etal. On the minimal rank of not necessarily symmetric matrices: a preliminary study[J]. Electron J Linear Algebra, 2009,18:126-145.

[4] BARRETTE W, VAN DER HOLST H, LOEWY R. Graphs whose minimalrank is two[J]. Electron J Linear Algera, 2004,11:258-280.

[5] BARRETTE W, VAN DER HOLST H, LOEWY R. Graphs whose minimalrank is two: the finite fields case[J]. Electron J Linear Algebra, 2005,14:32-42.

[6] BARRETTE W, GROUT J, LOEWY R. The minimal rank problem over the finite field of order 2:minimum rank 3[J]. Linear Algebra Appl, 2009,431(4):890-923.

[7] DEALBA L, GROUT J, HOGBEN L,etal. Universally optimal matrices and field indepence of the minimum rank of a graph[J]. Electron J Linear Algebra, 2009,18:403-419.

[8] FALLAT S M, HOGBEN L. The minimum rank of symmetric matrices described by a graph: a survey[J]. Linear Algera Appl, 2007,426(2-3):558-582.

[9] HOGBEN L. Minimum rank problems[J]. Linear Algera Appl, 2010,432(8):1961-1974.

[10] SHEN X, HOU Y, SHENG L. On the minimum rank of third power of a starlike tree[J]. Linear Algera Appl, 2012,436(12):4503-4511.

[11] ALLISON M, BODINE E, DEALBA L M,etal. Minimum rank of skew-symmetric matrices described by a graph[J]. Linear Algebra Appl, 2010,432(10):2457-472.

[12] DEALBA L, KERZNER E, TUCKER S. A note on the minimum skew rank of powers of paths[EB/OL]. http://cn.arxiv.org/abs/1107.2450v1.

[13] 盛 立.圖的最小反秩[D].長沙：湖南師范大學碩士學位論文, 2011.

(編輯 沈小玲)

Minimum Skew-Rank ofr- Power of Caterpillars

SHENXiao-ling*,HOUYao-ping

(College of Mathematics and Computer Science, Hunan Normal University, Changsha 410081, China)

The minimum skew-rank of a simple graphGis the smallest possible rank among all skew-symmetric matrices overF. The minimum skew-rank ofr-power of caterpillar is characterized by using constructing matrices and zero-forcing. LetTnbe a caterpillar, andn,rare all positive integers,ris odd, then

minimum skew-rank; skew-symmetric matrix;r-power of caterpillars

2014-04-20

國家自然科學基金資助項目(10771061);湖南省自然科學基金資助項目(14JJ7036)

*

,E-mail：185869458@qq.com

O151.21

A

1000-2537(2014)04-0087-05