Wenger圖的控制數(shù)

劉　凌

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

?

Wenger圖的控制數(shù)

劉凌

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

1問題的提出

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

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

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

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

同樣,可定義X在Y中的控制數(shù)

易見,二部圖G的控制數(shù)

設(shè)v是圖G中的一個點,G中與點v相關(guān)聯(lián)的邊的條數(shù)稱為點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)

的解,其系數(shù)矩陣

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

2Wenger圖Hm(q)的控制數(shù)

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

引理1設(shè)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設(shè)a∈Fq,則M={[a1,…am-1,a]T|a1,…,am-1∈Fq}?X為Hm(q)中Y在X中的控制集,并且Y在X中的控制數(shù)為qm-1.

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

引理2設(shè)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)的控制數(shù)γ(G)=ξ(Y)+η(X)可知,Wenger圖Hm(q)的控制數(shù)為Y在X中的控制數(shù)qm-1與X在Y中的控制數(shù)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].上海理工大學(xué)學(xué)報,2013,35(1):21-26.

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

[6]沈富強,吳寶豐.最小Q-特征值為給定整數(shù)的一類圖[J].上海理工大學(xué)學(xué)報,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]張先迪,李正良.圖論及其應(yīng)用[M].北京:高等教育出版社,2005.

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

(編輯:石瑛)

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

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

關(guān)鍵詞：二部圖; Wenger圖; 控制集; 控制數(shù)

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

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

收稿日期：2014-09-18

DOI：10.13255/j.cnki.jusst.2015.06.003

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

中圖分類號：O 157.5

文獻標志碼：A