圈與路的笛卡爾乘積的配對控制數(shù)

圈與路的笛卡爾乘積的配對控制數(shù)

黃海圓

（浙江師范大學(xué)數(shù)理與信息工程學(xué)院，浙江金華321004）

根據(jù)Cn×Pm的結(jié)構(gòu)特點(diǎn),利用配對控制數(shù)的定義及反證法,確定了圈與路的笛卡爾乘積圖Cn×Pm(m=2;3)的配對控制數(shù).

笛卡爾乘積；控制數(shù)；全控制數(shù)；配對控制數(shù)

關(guān)于圖的笛卡爾乘積的相關(guān)控制數(shù)已經(jīng)有了很多結(jié)論.2001年,Proffitt等確定了γp(Pn×Pm)的值，其中m=2;3［1］；由Gravier關(guān)于全控制數(shù)的結(jié)論可以得到γ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)的配對控制數(shù).

1 預(yù)備知識(shí)

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

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

引理1［3］對任意的圖

2 主要結(jié)果

定理1當(dāng)n≥3時(shí)，

證由引理1可得,

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

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

引理2當(dāng)n≥時(shí)，γt(Cn×P3)=n.

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

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

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

設(shè)Yi是Cn×P3中下標(biāo)最小的零列，下標(biāo)模n.則對任意的j〈i，都有|Yj∩D|=1.否則,(D∪j〈i(Yj∩D))∪(∪j≤i{uj, v1})，或者是比D更小的全控制集，或者是基數(shù)|D|為但零列比D更少的全控制集，矛盾.由此可得，?j〈i，有(uj,v1)∈D.又(ui,v0),(ui,v2)被D中的點(diǎn)控制，故(ui+1,v0),(ui+1,v2)∈D.又因?yàn)镈是全控制集，則有(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)是基數(shù)比D更少的全控制集,矛盾.因此(ui+2,v2)?D.從而(D {(ui+1,v0),(ui+1,v2)})∪{(ui,v1),(ui+2,v1)}是基數(shù)為|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)是基數(shù)為|D|但零列比D更少的全控制集，矛盾.因此(ui+1,v1)?D.若(ui+2,v1)∈D,則(D{(ui+1,v0),(ui+1,v2)})∪{(ui,v1),(ui+1,v1)}是基數(shù)為|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)是基數(shù)為|D|但零列比D更少的全控制集,矛盾.因此|Yi+3∩D|≥1.

當(dāng)|Yi+3∩D|=1時(shí).

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

當(dāng)|Yi+3∩D|≥2時(shí).

若Yi+3中含D的兩個(gè)點(diǎn)并且這兩個(gè)點(diǎn)兩兩相鄰,或者Yi+3中的三個(gè)點(diǎn)都包含在D中.則集合(D{(ui+1,v0), (ui+1,v2),(ui+2,v0),(ui+2,v2)})∪{(ui,v1),(ui+1,v1),(ui+2,v1)}是基數(shù)比D更小的全控制集，矛盾.因此，Yi+3中含D的兩個(gè)點(diǎn)不相鄰.因?yàn)?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))是基數(shù)為|D|但零列比D更少的全控制集，矛盾.

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

定理2當(dāng)n≥3時(shí),

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

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

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

又因?yàn)榕鋵刂茢?shù)是偶數(shù)，所以當(dāng)n≡0(mod 2)時(shí),γp(Cn×P3)≥n.當(dāng)n≡1(mod 2)時(shí),γp(Cn×P3)≤n+1.

綜上，結(jié)論得證.

［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］連小娟,裴利丹,潘向峰.路與圈的笛卡爾乘積的全控制數(shù)［J］.合肥學(xué)院學(xué)報(bào)：自然科學(xué)版,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

（責(zé)任編輯：邵曉軍）

2015-01-27

國家自然科學(xué)基金項(xiàng)目(11101378).

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