路与圈的笛卡尔乘积的配对控制数*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的笛卡尔积……