张晓转, 孟 巍

(山西大学 数学科学学院，山西 太原 030006)

设S是有向图D的顶点集V的一个子集,如果N+[S]=V,则称S是有向图D的一个控制集[1].有向图D中最小控制集的阶称为D的控制数,记作γ(D)[1].设k是一个正整数,S是有向图D中V的一个顶点子集,如果|N-(v)∩S|≥k对于每个v∈VS均成立,则称S是有向图D中的一个k-控制集.有向图D中最小k-控制集的阶称为k-控制数,记作γk(D).有向图D中的一个阶数最小的k-控制集叫做γk(D)-集.有向图D中的一个阶数最小的1-控制集叫做γ(D)-集.

图的控制参数是图的一个重要参数,它与染色体,划分数等其他参数有着密切的联系,并且它与组合优化,理论计算机科学等其他学科领域都有着密切的联系.基于不同的实际背景,图论研究者在图的控制理论的基础上定义了许多图的控制参数,比如图的符号控制,图的k-距离控制,图的Roman控制等.2004年,Cockayne[2]等给出了无向图的Roman控制函数的定义及其相关结论.后来,Lutz[1]将它推广到了有向图中,给出了有向图的Roman控制函数.称函数f:V→{0,1,2}为有向图D的一个Roman控制函数,如果对于每个f(v)=0的顶点v都至少有一个入邻点w满足f(w)=2.Roman控制函数f权值是指在函数f作用下各个顶点的值的和,即ω(f)=∑v∈Vf(v).有向图D的权值最小的Roman控制函数的权值称作有向图D的Roman控制数,记作γR(D).如果函数f是Roman控制函数并且ω(f)=γR(D),则称f是γR(D)-函数.

Kammerling和Volkmann[3]推广了无向图的Roman控制函数,得到了无向图的罗马Romank-控制函数并且给出了关于无向图的Romank-控制函数的大量结果.设k是一个正整数,称函数f:V→{0,1,2}是无向图G的一个Romank-控制函数,如果对于每个f(v)=0的顶……