劉　凌

(上海理工大學 理學院,上海　200093)

?

Wenger圖的控制數

劉凌

(上海理工大學 理學院,上海200093)

1問題的提出

這些結論對于研究極值圖論中偶圈的Turán數的精確階都有十分重要的意義[4-6].在文獻[7]中,Viglione確定了Hm(q)的直徑(圖中任意兩點間距離的最大值).受此啟發(fā),本文將研究Hm(q)的另一個結構參數——控制數.

首先給出Wenger圖Hm(q)和控制數的定義.

定義2[8-10]設G=(V,E)為一個圖,D?V,若對每一個v∈VD,存在u∈D,使uv∈E,則稱D為圖G的一個控制集,G的控制數

定義3設G=(X∪Y,E)為一個二部圖,M?X,若對于每個v∈Y,存在u∈M,使uv∈E,則稱M為Y在X中的一個控制集,Y在X中的控制數

同樣,可定義X在Y中的控制數

易見,二部圖G的控制數

設v是圖G中的一個點,G中與點v相關聯的邊的條數稱為點v的度,用d(v)表示.下面的命題1在文獻[1]中已有證明,為了文章的完整性,這里給出了它的另一種證明.

命題1在Hm(q)中,對任意的A∈X,B∈Y,都有A與B的度相等,都為q.

證明由Hm(q)圖中AB相鄰的定義,可知A的度必為q,又對任意B=[b1,b2,…,bm]T∈Y,若A=[a1,a2,…,am]T∈X，A與B相連,則a1,a2,…,am為方程組

(1)

的解,其系數矩陣

的秩為m-1,從而方程組(1)的解空間維數為1,故X中恰有q個點與B相連,B的度也為q.

2Wenger圖Hm(q)的控制數

通過構造Hm(q)的一個控制集,并證明其是點數最小的控制集,從而確定Hm(q)的控制數.

引理1設a∈Fq,Hm(q)=(X∪Y,E),

則M中任意兩個不同的點都沒有公共鄰點.

故有

從而a1,m-1-a2,m-1=0,a1,m-2-a2,m-2=0,…,依此類推,a11-a21=0,故a1j=a2j,j=1,2…,m-1,即A1=A2,矛盾.

命題2設a∈Fq,則M={[a1,…am-1,a]T|a1,…,am-1∈Fq}?X為Hm(q)中Y在X中的控制集,并且Y在X中的控制數為qm-1.

證明由命題1,X中每一個點的度為q,M中共有qm-1個點,每個點的度均為q.又由下面的引理2可知,M中不同的A點一定與Y中不同的B點相連,從而Y中所有qm個點與M中點相連且沒有重復,M為Y在X中的控制集,并且是含有點數最少的控制集,從而Y在X中的控制數為qm-1.

引理2設b∈Fq,則N={[b1,…bm-1,b]T|b1,…,bm-1∈Fq}?Y,則N中任意兩個不同的點都沒有公共鄰點.

證明在N中任取兩個不同的點

b1j=b2j，j=1,2…,m-1,即B1=B2,矛盾.

與命題2同理得命題3.

命題4γ(Hm(q))=2qm-1.

證明由二部圖的G=(X∪Y,E)的控制數γ(G)=ξ(Y)+η(X)可知,Wenger圖Hm(q)的控制數為Y在X中的控制數qm-1與X在Y中的控制數qm-1之和.

參考文獻：

[1]Wenger R.Extremal graphs with noC4,C6orC10’s.[J].Journal of Combinational Theory Series B,1991,52(1):113-116.

[2]Shao J Y,He C X,Shan H Y.The existence of even cycles with specific lengths in wenger’s graph[J].Acta Mathematicae Applicatae Sinica,English Series,2008,24(2):281-288.

[3]Lazebnik F,Thomason A,Wang Y.On some cycles in Wenger Graphs[EB/OL].[2014-12-25].http://www.math.udel.edu/~lazebnik/papers/LazebnikTho-masonWang2014 Submitted.pdf.

[4]周敏,何常香.單圈圖依次小Q-特征值排序[J].上海理工大學學報,2013,35(1):21-26.

[5]徐麗珍,何常香.雙圈圖的無符號拉普拉斯特征多項式的系數[J].上海理工大學學報,2014,36(1):12-14.

[6]沈富強,吳寶豐.最小Q-特征值為給定整數的一類圖[J].上海理工大學學報,2014,36(5):425-428.

[7]Viglione R.On the diameter of wenger graphs[J].Acta Applicandae Mathematica,2008,104(2):173-176.

[8]Bondy J A,Murty U S R.Graph theory and its applications[M].New York:MacMillan Press,1976.

[9]張先迪,李正良.圖論及其應用[M].北京:高等教育出版社,2005.

[10]彭茂.圖的控制集的一些相關問題的研究[D].上海:上海交通大學,2008.

(編輯:石瑛)

第一作者： 馬杰(1975-),男,副教授.研究方向:功能納米材料的構筑與應用.E-mail:majie@usst.edu.cn

摘要：Wenger圖Hspan(q)是定義在有限域Fspan上的q-正則二部圖.根據二部圖G=(X∪Y,E)的控制數為Y在X中的控制數與X在Y中的控制數之和,采用矩陣運算的方法在Hspan(q)中通過構造含點數最少的控制集,說明了這兩個控制數應該相等,從而確定了Wenger圖的控制數.

關鍵詞：二部圖; Wenger圖; 控制集; 控制數

Domination Number of Wenger GraphLIU Ling

(College of Science,University of Shanghai for Science and Technology,Shanghai 200093,China)

Abstract：Wenger’s graph Hspan(q) is a q-regular bipartite graph in the field Fspan.Considering that the domination number of a bipartite graph G=(X∪Y,E) is the sum of Y’s domination number in X and X’s domination number in Y,by using the matrix operation,the domination set of Hspan(q) with minimum cardinality was constructed.It is proved that the two domination numbers are equal,and then the domination number of Hspan(q) was determined.

Key words：bipartite graph; Wenger graph; domination set; domination number

基金項目：上海市自然科學基金資助項目(15ZR1428500)

收稿日期：2014-09-18

DOI：10.13255/j.cnki.jusst.2015.06.003

文章編號：1007-6735(2015)06-0520-07

中圖分類號：O 157.5

文獻標志碼：A