圆的有向图的全控制数
2023-07-13张新鸿
张 越,张新鸿
(太原科技大学 应用科学学院,太原 030024)
1980年,全控制的概念被E.J.Cockayne等人提出[1]。1998年,Teresa Haynes、Stephen Hedetniemi和Peter Slater出版了两本关于“控制”的图书,其中首次对图论中的控制理论、算法和应用方面进行了全面的分析和讨论[2-3]。近年来,控制理论在通讯、计算机等很多方面也有了长足的发展[4-6]。
在有向图D中,设S∈V(D),如果D中每个点都至少控制S中的一个点,就称S是D的一个全控制集,具有最小基数的全控制集称为最小全控制集,其基数称为全控制数。圆的有向图D中v1,v2,…,vn满足圆序,且每个顶点满足:
{vi-d-(vi),…,vi-1},
其中i∈{1,2,…,n}.强连通是指在有向图中,既有从x到y的途径,也有从y到x的途径[7-12]。文中未提及的概念或符号参看文献[7].
1 圆的竞赛图的最小全控制集和全控制数
圆的竞赛图有n个顶点,且满足任意两点间都有弧且不存在2圈的图,其中顶点v1,v2,…,vn满足圆序,下标均模n.
定理1对于每个强连通竞赛图的任意一个顶点,都包含一个通过它的k圈,其中k=3,4,…,n且n∈Z[8].
引理1设T是一个n阶的竞赛图,则T的全控制数γt(D)≥3.
证明由全控制集的定义易知,T中任意一个顶点都不能构成T的一个全控制集。任取T中两个顶点vi,vj.因为T是一个竞赛图,故vi和vj之间有且仅有一条弧,不妨设vivj∈A(t).令M={vi,vj}.容易看出,M中不存在顶点v使得vi→v.由全控制集的定义可知,M不是T的一个全控制集,再由vi,vj的任意性,可知γt(D)≥3.
定理2若一个n阶的圆的竞赛图D是强连通的,v1,v2,…,vn满足圆序,则{vi,vj,vk}⊆V(D)是D的最小全控制集,当且仅当vi→vj→vk→vi,且所有顶点的下标均是模n的。
证明(必要性)任取顶点子集M′={x,y,z}⊆V(D),且x,y,z不构成D中的3圈,由D是一个竞赛图可知,M′中必有一个顶点被其它两个顶点控制。……
