圈與路的笛卡爾乘積的配對控制數

圈與路的笛卡爾乘積的配對控制數

黃海圓

（浙江師范大學數理與信息工程學院，浙江金華321004）

根據Cn×Pm的結構特點,利用配對控制數的定義及反證法,確定了圈與路的笛卡爾乘積圖Cn×Pm(m=2;3)的配對控制數.

笛卡爾乘積；控制數；全控制數；配對控制數

關于圖的笛卡爾乘積的相關控制數已經有了很多結論.2001年,Proffitt等確定了γp(Pn×Pm)的值，其中m=2;3［1］；由Gravier關于全控制數的結論可以得到γp(Pn×P4)的確定值［2］；2008年,Brsˇar等確定了γp(Cn×C4),其中n≥3［3］；2013年,裴利丹等確定了γt(Pn×Cm)其中m=3,4以及γt(Cn×Pm)其中m=2,4［5］.2014年,Hu等確定了γp(Cn×Cm)的值,其中n≥3,m=3,4［4］.本文主要討論笛卡爾乘積圖Cn×Pm(m=2,3)的配對控制數.

1 預備知識

設G=(V;E)是頂點集為V,邊集為E的圖.用|G|表示圖G的階數.圖G中的一個頂點u的開鄰域為N(u)= {v∈V|uv∈E}，點u的閉鄰域為N［u］=N(u)∪{u}.稱G中與u相關聯的邊的條數為u在G中的度數，記Δ為G的最大度.匹配M是G中兩兩不相鄰的邊組成的集合.若?v∈V,M中都有邊關聯v,則稱M是G的一個完美匹配.非空子集D?V,若?v∈VD都有N(v)∩D≠φ成立,則稱D是G的控制集.G中控制集的最小基數稱為G的控制數，記為γ(G).若?v∈V都有N(v)∩D≠φ成立,則稱D是G的全控制集.G中全控制集的最小基數稱為G的全控制數，記為γt(G).若D是控制集，且由D導出的子圖G［D］包含一個完美匹配M，則稱D是配對控制集.G中最小配對控制集的基數稱為G的配對控制數，記為γp(G).G×H是兩個圖G=(V1,E1)和H=(V2,E2)的笛卡爾乘積圖,G×H的頂點集為V(G×H)={(u,v)|u∈V1;v∈V2}.其中(u,v)，(u′,v′)相鄰當且僅當u=u′且vv′∈E2,或者v=v′且uu′∈E1.

首先給出幾個記號及引理.用Cn和Pn分別表示階為n(n≥2)的圈和路,且將Cn的點標記為u0,u1…,un-1,Pn的點標記為v0,v1…,vn-1.記Cn×Pm為Cn與Pm的笛卡爾乘積,其頂點集為V(Cn×Pm)={(ui,vj)|ui∈V(Cn),vj∈V (Pm)}.記Yi={(ui,vj)|0≤j≤m-1}，則Yi為Cn×Pm的列.

引理1［3］對任意的圖

2 主要結果

定理1當n≥3時，

證由引理1可得,

另一方面,當n=0,2(mod 3)時,D={(ui,v0),(ui,v1)：i≡0(mod 3)}是Cn×P2的基數為]的配對控制集,故γp

當n≡1(mod 3)時,D={(ui,v0),(ui,v1)：i≡0(mod 3)}∪{(un-2,v0),(un-2,v1)是Cn×P2的基數為]的配對控制集,故

引理2當n≥時，γt(Cn×P3)=n.

證令D′{(ui,v1)：0≤i≤n-1},則D′是Cn×P3的全控制集.故γt(Cn×P3)≤n.

下面證明D′是Cn×P3的最小全控制集.

假設存在D使得|D|〈|D′|是Cn×P3的最小全控制集，則|D|≤n-1.因此，Cn×P3中至少有一列交D為空.設Cn×P3中交D為空的列為零列.選取Cn×P3的最小全控制集D,使得它含最少的零列.

設Yi是Cn×P3中下標最小的零列，下標模n.則對任意的j〈i，都有|Yj∩D|=1.否則,(D∪j〈i(Yj∩D))∪(∪j≤i{uj, v1})，或者是比D更小的全控制集，或者是基數|D|為但零列比D更少的全控制集，矛盾.由此可得，?j〈i，有(uj,v1)∈D.又(ui,v0),(ui,v2)被D中的點控制，故(ui+1,v0),(ui+1,v2)∈D.又因為D是全控制集，則有(ui+1,v1)∈D或者(ui+2,v0),(ui+2,v2)∈D.分兩種情形討論：

情形1(ui+1,v1)∈D.

若(ui+2,v1)∈D,則(D{(ui+1,v0),(ui+1,v2)})∪(ui,v1)是基數比D更少的全控制集,矛盾.因此(ui+2,v2)?D.從而(D {(ui+1,v0),(ui+1,v2)})∪{(ui,v1),(ui+2,v1)}是基數為|D|但零列比D更少的全控制集，矛盾.

情形2(ui+2,v0),(ui+2,v2)∈D.

若(ui+1,v1)∈D,則(D{(ui+1,v0),(ui+1,v2)})∪(ui,v1),(ui+2,v1)是基數為|D|但零列比D更少的全控制集，矛盾.因此(ui+1,v1)?D.若(ui+2,v1)∈D,則(D{(ui+1,v0),(ui+1,v2)})∪{(ui,v1),(ui+1,v1)}是基數為|D|但零列比D更少的全控制集,矛盾.因此(ui+2,v1)?D.若Yi+3是Cn×P3中的零列,則(D{(ui+1,v0),(ui+1,v2),(ui+2,v0),(ui+2,v2)})∪{(ui,v1),(ui+1,v1),(ui+2,v1)}, (ui+3,v1)是基數為|D|但零列比D更少的全控制集,矛盾.因此|Yi+3∩D|≥1.

當|Yi+3∩D|=1時.

若(ui+3,v0)∈D,則(D{(ui+1,v0),(ui+1,v2),(ui+2,v0),(ui+2,v2)})∪{(ui,v1),(ui+1,v1),(ui+2,v1),(ui+3,v1)}是基數為|D|但零列比D更少的全控制集，矛盾.若(ui+3,v2)∈D,由Cn×P3的對稱性，類似(ui+3,v0)∈D的討論可以得到一個基數為|D|但零列比D更少的全控制集,矛盾.若(ui+3,v1)∈D，則集合(D{(ui+1,v0),(ui+1,v2),∪{(ui,v1),(ui+1,v1),(ui+2,v1)}是基數比D更小的全控制集,矛盾.

當|Yi+3∩D|≥2時.

若Yi+3中含D的兩個點并且這兩個點兩兩相鄰,或者Yi+3中的三個點都包含在D中.則集合(D{(ui+1,v0), (ui+1,v2),(ui+2,v0),(ui+2,v2)})∪{(ui,v1),(ui+1,v1),(ui+2,v1)}是基數比D更小的全控制集，矛盾.因此，Yi+3中含D的兩個點不相鄰.因為(ui+1,v1),(ui+2,v1)?D,所以可以得到集合(D{(ui+1,v0),(ui+1,v2),(ui+2,v0),(ui+2,v2)})∪{(ui,v1),(ui+1,v1),(ui+2, v1)},(ui+3,v1))是基數為|D|但零列比D更少的全控制集，矛盾.

綜上，γt(Cn×P3)=n.

定理2當n≥3時,

證當n≡0(mod 2)時,令D={(ui,v1)：0≤i≤n-1}是Cn×P3的基數為n的配對控制集.因此γp(Cn×P3)≤n.

當n≡1(mod 2)時,令D={(ui,v1)：0≤i≤n-1}∪{(un-1,v0)}是Cn×P3的基數為n+1配對控制集.因此γp(Cn×P3)≤n+1.

另一方面，由引理2及γt(Cn×P3)≤γp(Cn×P3)可以得到，γp(Cn×P3)≥n.

又因為配對控制數是偶數，所以當n≡0(mod 2)時,γp(Cn×P3)≥n.當n≡1(mod 2)時,γp(Cn×P3)≤n+1.

綜上，結論得證.

［1］Proffitt K E,Haynes T W,Slater P J.Paired-domination in grid graphs［J］.Congressus Numerantium,2001(150):161-172.

［2］Gravier S.Total domination number of grid graphs［J］.Discrete Applied Mathematics,2002,121(1):119-128.

［3］Br?ar B,Henning M A,Rall D F.Rainbow domination in graphs［J］.Taiwanese Journal of Mathematics,2008,12(1):213-225.

［4］Hu F T,Xu J M.Total and paired domination numbers of toroidal meshes［J］.Journal of Combinatorial Optimization,2014,27(2): 369-378.

［5］連小娟,裴利丹,潘向峰.路與圈的笛卡爾乘積的全控制數［J］.合肥學院學報：自然科學版,2014,24(1):7-9.

Paired Domination Number of the Cartesian Products of Cycles With Paths

HUANG Hai-yuan
（College of Mathematics，Physics and Information Engineering，Zhejiang Normal University，Jinhua 321004,Zhejiang,China）

According to the structure of Cn×Pmand the definition of paired domination number，using contradiction method,the paper determined the paired domination number of the Cartesian product of Cn×Pm(m=2;3).

Cartesian product graph；domination number；total domination number；paired domination number

O157.5

：A

：1007-5348（2015）04-0001-03

（責任編輯：邵曉軍）

2015-01-27

國家自然科學基金項目(11101378).

黃海圓（1990-），女，江西上饒人，浙江師范大學數理與信息工程學院碩士研究生；研究方向：圖論.