黃海圓, 馬美杰

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

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

黃海圓, 馬美杰

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

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

笛卡爾乘積;控制集;控制數(shù);配對(duì)控制集;配對(duì)控制數(shù)

本文僅討論無環(huán)、無重邊、無孤立點(diǎn)的無向圖.設(shè)G=(V,E)是頂點(diǎn)集為V、邊集為E的圖.圖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)為G的最大度.圖G′=(V′,E′)是圖G=(V,E)的生成子圖,其中E′?E,V′=V.匹配M是G中兩兩不相鄰的邊組成的集合.若?v∈V,M中都有邊關(guān)聯(lián)v,則稱M是G的一個(gè)完美匹配.非空子集D?V,若對(duì)?x∈VD都有N(x)∩D≠?成立,則稱D是G的控制集.稱G中控制集的最小基數(shù)為G的控制數(shù),記為γ(G).若D是控制集,且由D導(dǎo)出的子圖G[D]包含一個(gè)完美匹配M,則稱D是配對(duì)控制集.稱G中最小配對(duì)控制集的頂點(diǎn)數(shù)為G的配對(duì)控制數(shù),記為γp(G).稱匹配M中的邊連接的2個(gè)點(diǎn)為D的對(duì).G×H是2個(gè)圖G=(V1,E1)和H=(V2,E2)的笛卡爾乘積圖,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.

關(guān)于圖的笛卡爾乘積的相關(guān)控制數(shù)已經(jīng)有了很多結(jié)論.2001年,Proffitt等[1]確定了γp(Pn×Pm)的值,其中m=2,3;由Gravier[2]關(guān)于全控制數(shù)的結(jié)論可以得到γp(Pn×P4)的確定值;2008年,Bre?ar等[3]確定了γp(Cn×C4)的值,其中n≥3;2014年,文獻(xiàn)[4]確定了γp(Cn×Cm)的值,其中n≥3,m=3,4;2013年,裴利丹等[5]確定了γ(Pn×Cm)的值,其中m=3,4.本文主要討論笛卡爾乘積圖Pn×Cm(m=3,4)的配對(duì)控制數(shù).

首先給出幾個(gè)記號(hào)及引理.分別用Cn和Pn表示階為n(n≥2)的圈和路,且將Cn,Pn的點(diǎn)標(biāo)記為0,1,…,n-1.記Pn×Cm為Pn與Cm的笛卡爾積,V(Pn×Cm)={(i,j) |i∈V(Pn),j∈V(Cm)};記Yi={(i,j) | 0≤j≤m-1},0≤i≤n-1,則Yi為Pn×Cm的列.令Hji=Yi∪Yi+1∪… ∪Yi+j-1,i+j≤n.

引理2[4]當(dāng)n≥3時(shí),

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

引理4當(dāng)n≥5時(shí),令D是Pn×C3的配對(duì)控制集,則|D∩H5i|≥4,0≤i≤n-5.

證明 設(shè)S=D∩H5i,其中H5i=Yi∪Yi+1∪… ∪Yi+4,0≤i≤n-5.令S1=D∩H3i+1,其中H3i+1=Yi+1∪Yi+2∪Yi+3.由D是配對(duì)控制集及圖的結(jié)構(gòu)知,點(diǎn)集S控制子圖H3i+1.

1)D∩Yi+2=?.因?yàn)辄c(diǎn)集D中的一個(gè)點(diǎn)至多控制Yi+2中的一個(gè)點(diǎn),且控制Yi+2的點(diǎn)都在Yi+1∪Yi+3中,又|Yi+2|=3,所以|S1|=|D∩H3i+1|≥3.由于D是Pn×C3的配對(duì)控制集,且與S1配對(duì)的點(diǎn)都在H5i中,所以|S|≥4.

2)D∩Yi+2≠?.因?yàn)镈是Pn×C3的配對(duì)控制集,所以|S1|≥2.若|S1|≥3,則由上面的證明知|S|≥4.若|S1|=2,即S1是2個(gè)相鄰的點(diǎn)集,則圖H3i+1中2個(gè)相鄰的點(diǎn)至多控制H3i+1中的7個(gè)點(diǎn).而|H3i+1|=9,故點(diǎn)集D在Yi∪Yi+4中至少有2個(gè)點(diǎn)控制H3i+1中沒有被S1控制的點(diǎn).因此，|S|≥4.引理4證畢.

1)|D∩Y0|=0.因?yàn)镈控制Y0中的點(diǎn),故Y1?D.由D是配對(duì)控制集知,Y2中有一個(gè)點(diǎn)屬于D.因此，D∩I0?Y1∪Y2,從而Y3中有2個(gè)點(diǎn)不能被D∩I0控制.矛盾.

2)|D∩Y0|=3.由D是配對(duì)控制集知,Y1中有一個(gè)點(diǎn)屬于D.因此,D∩I0?Y0∪Y1,從而Y3中的點(diǎn)都不能被D∩I0控制.矛盾.

3)|D∩Y0|=2.因?yàn)镈∩I0控制Y0∪Y1∪Y2∪Y3,所以|D∩(Y1∪Y2)|≥1.因此,|D∩Y3|≤1,D∩Y4=?.從而Y4中至少有2個(gè)點(diǎn)沒被D∩I0控制,所以|D∩Y5|≥2.若|D∩Y5|=3,則與2)類似可以得到矛盾.因此,|D∩Y5|= 2,從而Y9中至少有2個(gè)點(diǎn)沒被D∩I1控制.依此類推,Yn-1中有點(diǎn)沒被D控制.矛盾.

4)|D∩Y0|=1.因D是配對(duì)控制集,故|D∩Y1|≥1.若|D∩Y1|≥2,則D∩(Y3∪Y4)= ?.從而D∩I0不能控制Y4中的點(diǎn).因此,Y5?D.從而與2)類似可以得到矛盾.若|D∩Y1|=1,則|D∩(Y2∪Y3)|=2.從而Y4中至少有一點(diǎn)沒被D∩I0控制,所以|D∩Y5|≥1.若|D∩Y5|≥2,則與2),3)類似可以得到矛盾.因此,|D∩Y5|=1,從而Y9中至少有一點(diǎn)沒被D∩I1控制.依此類推,Yn-1中至少有一點(diǎn)沒被D控制.矛盾.

由γp(P1×C3)=γp(P2×C3)=2及引理3和引理5可得以下結(jié)論:

圖1 P9×C4的配對(duì)控制集(實(shí)點(diǎn))

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

引理6當(dāng)n≥1且n≡1,3(mod 4)時(shí),γp(Pn×C4)=n+1.

證明 當(dāng)n≡1(mod 4)時(shí),D={(i,0),(i,1),(i+2,2),(i+2,3):i≡0(mod 4),i≠n-1}∪{(n-1,0),(n-1,1)}是Pn×C4基數(shù)為n+1的配對(duì)控制集,如圖1所示.

當(dāng)n≡3(mod 4)時(shí),D={(i,0),(i,1),(i+2,2),(i+2,3):i≡0(mod 4)}是Pn×C4基數(shù)為n+1的配對(duì)控制集.因此,當(dāng)n≡1,3(mod 4)時(shí),γp(Pn×C4)≤n+1.

當(dāng)n≡1,3(mod 4)時(shí),γp(Pn×C4)≥n+1.因此,γp(Pn×C4)=n+1.引理6證畢.

引理7當(dāng)n≥2且n≡0,2(mod 4)時(shí),γp(Pn×C4)=n+2.

4)|D∩Y0|= 2.

因此,γp(Pn×C4)>n.又因?yàn)榕鋵?duì)控制數(shù)是偶數(shù),所以γp(Pn×C4)≥n+2.

另一方面,當(dāng)n≡0(mod 4)時(shí),D={(i,0),(i,1),(i+2,2),(i+2,3):i≡0(mod 4)}∪{(n-1,0),(n-1,1)}是Pn×C4基數(shù)為n+2的配對(duì)控制集,當(dāng)n≡2(mod 4)時(shí),D={(i,0),(i,1),(i+2,2),(i+2,3):i≡0(mod 4),i≤n-3}∪{(n-2,0),(n-2,1),(n-1,0),(n-1,1)}是Pn×C4基數(shù)為n+2的配對(duì)控制集.因此,當(dāng)n≡0,2(mod 4)時(shí),γp(Pn×C4)≤n+2.引理7證畢.

由引理6和引理7可得以下結(jié)論:

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

[1]Proffitt K E,Haynes T W,Slater P J.Paired-domination in grid graphs[J].Cong Numer,2001,150:161-172.

[2]Gravier S.Total domination number of grid graphs[J].Discrete Appl Math,2002,121(1):119-128.

[3]Bre?ar B,Henning M A,Rall D F.Rainbow domination in graphs[J].Taiwanese J Math,2008,12(1):213-225.

[4]Hu Futao,Xu Junming.Total and paired domination numbers of toroidal meshes[J].J Comb Optim,2014,27(2):369-378.

[5]裴利丹,連小娟,潘向峰.路與圈的笛卡爾乘積的控制數(shù)[J].合肥學(xué)院學(xué)報(bào):自然科學(xué)版,2013,23(3):24-28.

(責(zé)任編輯 陶立方)

PaireddominationnumberoftheCartesianproductsofpathswithcycles

HUANG Haiyuan, MA Meijie

(CollegeofMathematics,PhysicsandInformationEngineering,ZhejiangNormalUniversity,JinhuaZhejiang321004,China)

Based on the structure ofPn×Cmand the definition of paired domination number, by using the induction and contradiction method, it was determined the paired domination number of the Cartesian product ofPn×Cm(m=3,4).

Cartesian product graph; domination set; domination number; paired domination set; paired domination number

10.16218/j.issn.1001-5051.2015.02.008

2014-09-07

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

黃海圓(1990-),女,江西上饒人,碩士研究生.研究方向:圖論.

馬美杰.E-mail: mameij@zjnu.cn

O157.5

A

1001-5051(2015)02-0172-04