有向图的外独立双罗马控制

作者：张新鸿^*; 代潇娜; 李瑞娟

来源：高校应用数学学报A辑(中文版), 2023, 38(04): 491-500.

DOI：10.13299/j.cnki.amjcu.002286

• 有向图
• 外独立双罗马控制
• 外树
• Nordhaus-Gaddum不等式

设D=(V (D), A(D))是一个有向图,若函数h:V (D)→{0, 1, 2, 3}满足以下条件:(1)每个赋值为0的顶点至少有一个赋值为3的内邻或两个赋值为2的内邻;(2)每个赋值为1的顶点至少有一个赋值为2或3的内邻;(3)所有赋值为0的顶点都是不相邻的,则称函数h为有向图D的一个外独立双罗马控制函数.一个有向图的外独立双罗马控制函数的权为所有顶点的赋值之和.外独立双罗马控制函数的最小权称为外独立双罗马控制数. 2020年, Abdollahzadeh Ahangar等人给出了无向图的外独立双罗马控制函数的定义,并给出了无向图外独立双罗马控制数的一些界.文中将此概念推广到了有向图上,研究了有向图的外独立双罗马控制数的界,并进一步刻画了外树的外独立双罗马控制数的下界,以及外独立双罗马控制数的Nordhaus-Gaddum不等式.

• 单位
  太原科技大学; 山西大学