宋 曦,陈 琴

(中国计量大学 理学院,浙江 杭州 310018)

图的控制理论主要研究图的各种控制参数的值。1962年Oystein正式提出“控制数”的概念并于1965年发表成果[1],之后有关图的控制数问题得到了迅速发展。控制集和控制数的重要性不仅仅体现在理论上,而且在生活中的应用也十分广泛。在许多选址问题上都需要借鉴控制数问题,比如在某个城市的小区之间建立快递物流服务站,最少需要建立多少个服务站才能保证物流运输的畅通。而在实际生活的各种要求限制下,又延伸出许多不同类别的控制数问题,如全控制数[2]、罗马控制数[3]等。赵敏和陈琴[4]将图的控制理论与电力网相结合,研究了几类电力控制数为1的平方图。Goddard等[5]在2014年提出并研究了图的半全控制集,此后许多学者对该问题进行了研究,并取得丰硕的成果。朱恩强等研究了无爪三正则图[6]、线图[7]的半全控制数。2019年,Henning等[8]证明了平面图、分裂图、弦二部图的半全控制数对应的判定问题是NP-完备的。陈琴等[9]研究了图的半全控制数的剖分数。

1 准备工作设

G=(V,E)是一个无向简单图,其中V是G的顶点集,E是G的边集。对于集合D⊆V,若VD中每个顶点都至少与D中一个顶点相邻,则称D是G的一个控制集。G的控制数是G的最小控制集的顶点个数,用γ(G)表示。对于集合S⊆V,若S是G的控制集,且对于S中的每个顶点,在S中都存在另一个顶点与其距离小于等于2,则称S是G的半全控制集。G的最小半全控制集的顶点个数称为G的半全控制数,记为γt2(G)。对任意的v∈V,v的开邻域记为N(v)={u∈V|uv∈E},闭邻域记为N[v]={v}∪N(v)。……