郝国亮,吴愉琪,曾淑婷

(1.东华理工大学理学院,江西 南昌 330013;2.菏泽学院数学与统计学院,山东 菏泽 274015)

1 预备知识

近几十年来,基于不同的应用背景,图的控制参数问题得到了广泛研究.[1-2]1999年,Stewart[3]提出了君士坦丁大帝时期防御罗马帝国的策略“Defend the Roman Empire”.基于该策略,Cockayne等[4]引入了图的罗马控制的概念.2016年,Chellali等[5]将“Defend the Roman Empire”中的防御策略弱化,提出了图的罗马{2}-控制数的概念.随后,罗马{2}-控制被Henning等[6]重新命名为意大利控制.Gao等[7]计算了笛卡尔乘积图的意大利控制数的精确值.Varghese等[8]研究了边的增加对意大利控制数的影响.Banerjee等[9]给出了计算余图的完美意大利控制数的线性时间算法.本文将研究图的全局意大利控制问题,给出了一般图的全局意大利控制数的界并且得到了某些特殊图的全局意大利控制数的精确值.

2 主要结论及其证明

命题1 对任意n阶图G,min{n,4}≤γgI(G)≤n.

由于0

证明当n∈{3,4}时,由命题1知,γgI(Fn)=n.设n≥5且设扇形图Fn是由路Pn-1=v2v3…vn和一个不在路Pn-1上的顶点v1组成,且使得v1与其他顶点都相邻.

若5≤n≤10,由命题1,要证明γgI(Fn)=4成立,只需要证明γgI(Fn)≤4即可.如果n=5,则定义F5的全局意大利控制函数g使得g(v5)=0,且当i≠5时g(vi)=1,于是γgI(F5)≤ω(g)=4;如果n∈{6,7},则定义Fn的全局意大利控制函数g使得当i∈{1,2,5,6}时g(vi)=1,且当i∉{1,2,5,6}时g(vi)=0,于是γgI(Fn)≤ω(g)=4;如果n∈{8,9},则定义Fn的全局意大利控制函数g使得当i∈{1,2,5,8}时g(vi)=1,且当i∉{1,2,5,8}时g(vi)=0,于是γgI(Fn)≤ω(g)=4;如果n=10,则定义F10的全局意大利控制函数g使得当i∈{1,3,6,9}时g(vi)=1,且当i∉{1,3,6,9}时g(vi)=0,于是γgI(F10)≤ω(g)=4.

若n≥11,定义Fn的全局意大利控制函数g使得g(v1)=g(v2)=2,g(v3)=1且当i∉{1,2,3}时,g(vi)=0,故γgI(Fn)≤5.往证γgI(Fn)≥5.由命题1,只要证明γgI(Fn)≠4即可.反证法.假设γgI(Fn)=4,令f是γgI(Fn)-函数,则ω(f)=γgI(Fn)=4.

断言1f(v1)=1.

这与f是γgI(Fn)-函数矛盾.因此f(v1)=1.断言1得证.

断言2f(vi-1)+f(vi)+f(vi+1)≥1,其中3≤i≤n-1.

事实上,若……