路与圈的笛卡尔乘积的配对控制数*1

黄海圆, 马美杰

(浙江师范大学 数理与信息工程学院,浙江 金华 321004)

路与圈的笛卡尔乘积的配对控制数*1

黄海圆, 马美杰

(浙江师范大学 数理与信息工程学院,浙江 金华 321004)

根据Pn×Cm的结构特点,利用配对控制数的定义、归纳法及反证法,确定了路与圈的笛卡尔乘积图Pn×Cm(m=3,4)的配对控制数.

笛卡尔乘积;控制集;控制数;配对控制集;配对控制数

本文仅讨论无环、无重边、无孤立点的无向图.设G=(V,E)是顶点集为V、边集为E的图.图G中的一个顶点u的开邻域为N(u)={v∈V|uv∈E},点u的闭邻域为N[u]=N(u)∪{u}.称G中与u相关联的边的条数为u在G中的度数.记Δ(G)为G的最大度.图G′=(V′,E′)是图G=(V,E)的生成子图,其中E′⊂E,V′=V.匹配M是G中两两不相邻的边组成的集合.若∀v∈V,M中都有边关联v,则称M是G的一个完美匹配.非空子集D⊆V,若对∀x∈VD都有N(x)∩D≠Ø成立,则称D是G的控制集.称G中控制集的最小基数为G的控制数,记为γ(G).若D是控制集,且由D导出的子图G[D]包含一个完美匹配M,则称D是配对控制集.称G中最小配对控制集的顶点数为G的配对控制数,记为γp(G).称匹配M中的边连接的2个点为D的对.G×H是2个图G=(V1,E1)和H=(V2,E2)的笛卡尔乘积图,V(G×H)={(u,v) |u∈V1,v∈V2}.其中,(u,v),(u′,v′)相邻当且仅当u=u′且vv′∈E2,或者v=v′且uu′∈E1.

关于图的笛卡尔乘积的相关控制数已经有了很多结论.2001年,Proffitt等[1]确定了γp(Pn×Pm)的值,其中m=2,3;由Gravier[2]关于全控制数的结论可以得到γp(Pn×P4)的确定值;2008年,Brešar等[3]确定了γp(Cn×C4)的值,其中n≥3;2014年,文献[4]确定了γp(Cn×Cm)的值,其中n≥3,m=3,4;2013年,裴利丹等[5]确定了γ(Pn×Cm)的值,其中m=3,4.本文主要讨论笛卡尔乘积图Pn×Cm(m=3,4)的配对控制数.

首先给出几个记号及引理.分别用Cn和Pn表示阶为n(n≥2)的圈和路,且将Cn,Pn的点标记为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]当n≥3时,

引理3当n≥3时,

引理4当n≥5时,令D是Pn×C3的配对控制集,则|D∩H5i|≥4,0≤i≤n-5.

证明 设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是配对控制集及图的结构知,点集S控制子图H3i+1.

1)D∩Yi+2=Ø.因为点集D中的一个点至多控制Yi+2中的一个点,且控制Yi+2的点都在Yi+1∪Yi+3中,又|Yi+2|=3,所以|S1|=|D∩H3i+1|≥3.由于D是Pn×C3的配对控制集,且与S1配对的点都在H5i中,所以|S|≥4.

2)D∩Yi+2≠Ø.因为D是Pn×C3的配对控制集,所以|S1|≥2.若|S1|≥3,则由上面的证明知|S|≥4.若|S1|=2,即S1是2个相邻的点集,则图H3i+1中2个相邻的点至多控制H3i+1中的7个点.而|H3i+1|=9,故点集D在Yi∪Yi+4中至少有2个点控制H3i+1中没有被S1控制的点.因此，|S|≥4.引理4证毕.

1)|D∩Y0|=0.因为D控制Y0中的点,故Y1⊆D.由D是配对控制集知,Y2中有一个点属于D.因此，D∩I0⊆Y1∪Y2,从而Y3中有2个点不能被D∩I0控制.矛盾.

2)|D∩Y0|=3.由D是配对控制集知,Y1中有一个点属于D.因此,D∩I0⊆Y0∪Y1,从而Y3中的点都不能被D∩I0控制.矛盾.

3)|D∩Y0|=2.因为D∩I0控制Y0∪Y1∪Y2∪Y3,所以|D∩(Y1∪Y2)|≥1.因此,|D∩Y3|≤1,D∩Y4=Ø.从而Y4中至少有2个点没被D∩I0控制,所以|D∩Y5|≥2.若|D∩Y5|=3,则与2)类似可以得到矛盾.因此,|D∩Y5|= 2,从而Y9中至少有2个点没被D∩I1控制.依此类推,Yn-1中有点没被D控制.矛盾.

4)|D∩Y0|=1.因D是配对控制集,故|D∩Y1|≥1.若|D∩Y1|≥2,则D∩(Y3∪Y4)= Ø.从而D∩I0不能控制Y4中的点.因此,Y5⊂D.从而与2)类似可以得到矛盾.若|D∩Y1|=1,则|D∩(Y2∪Y3)|=2.从而Y4中至少有一点没被D∩I0控制,所以|D∩Y5|≥1.若|D∩Y5|≥2,则与2),3)类似可以得到矛盾.因此,|D∩Y5|=1,从而Y9中至少有一点没被D∩I1控制.依此类推,Yn-1中至少有一点没被D控制.矛盾.

由γp(P1×C3)=γp(P2×C3)=2及引理3和引理5可得以下结论:

图1 P9×C4的配对控制集(实点)

定理1当n≥1时,

引理6当n≥1且n≡1,3(mod 4)时,γp(Pn×C4)=n+1.

证明 当n≡1(mod 4)时,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基数为n+1的配对控制集,如图1所示.

当n≡3(mod 4)时,D={(i,0),(i,1),(i+2,2),(i+2,3):i≡0(mod 4)}是Pn×C4基数为n+1的配对控制集.因此,当n≡1,3(mod 4)时,γp(Pn×C4)≤n+1.

当n≡1,3(mod 4)时,γp(Pn×C4)≥n+1.因此,γp(Pn×C4)=n+1.引理6证毕.

引理7当n≥2且n≡0,2(mod 4)时,γp(Pn×C4)=n+2.

4)|D∩Y0|= 2.

因此,γp(Pn×C4)>n.又因为配对控制数是偶数,所以γp(Pn×C4)≥n+2.

另一方面,当n≡0(mod 4)时,D={(i,0),(i,1),(i+2,2),(i+2,3):i≡0(mod 4)}∪{(n-1,0),(n-1,1)}是Pn×C4基数为n+2的配对控制集,当n≡2(mod 4)时,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基数为n+2的配对控制集.因此,当n≡0,2(mod 4)时,γp(Pn×C4)≤n+2.引理7证毕.

由引理6和引理7可得以下结论:

定理2当n≥1时,

[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]裴利丹,连小娟,潘向峰.路与圈的笛卡尔乘积的控制数[J].合肥学院学报:自然科学版,2013,23(3):24-28.

(责任编辑 陶立方)

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

国家自然科学基金资助项目(11101378)

黄海圆(1990-),女,江西上饶人,硕士研究生.研究方向:图论.

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

O157.5

A

1001-5051(2015)02-0172-04