关于树结构中的独立半完全支配关系

《Discrete Applied Mathematics》：On the independent semitotal domination in trees

　　摘要：在一个连通图??中，如果集合??既是??的一个支配集，且??中的每个顶点都与其他某个顶点的距离不超过2，那么??被称为半完全支配集。如果此外??还是一个独立集，那么??被称为??的独立半完全支配集。图??的（独立）半完全支配数记为?????2?(??)（或?????2?(??)），它是所有（独立）半完全支配集中最小的基数。根据定义，对于每个连通的非完全图??，我们有?????2?(??)≤?????2?(??)。在本文中，我们确定了当??是至少三阶的树时?????2?(??)的下界和上界，并且当??是二叉树时得到了?????2?(??)的一个改进下界。最后，我们提供了所有满足?????2?(??)=?????2?(??)的树的构造性描述。

引言：在本文中，我们将??视为一个具有顶点集???(??)和边集???(??)的连通简单图。给定??中的一个顶点??，???(??)和???[??]分别表示??的开放邻域和闭合邻域。如果对于所有∈???(??)???的顶点??，都有???(??)∩??≠0?，那么顶点集??被称为??的一个支配集。关于图中的支配性质的全面调查可以在[7]、[8]中找到。半完全支配的概念是图论中经典支配性质的自然扩展。一个连通图??的半完全支配集是一个这样的支配集：??中的每个顶点都与其他某个顶点的距离不超过2。用?????2?(??)表示??所有半完全支配集的集合。然后定义图??的半完全支配数为?????2?(??)=min?{|??|:??∈?????2?(??)}。一个满足|??|=?????2?(??)的??集合被称为?????2?(??)集合。这个参数由Goddard等人在[5]中引入，并在[3]、[4]、[10]、[11]、[12]、[17]、[18]中进一步研究。最近，在[13]中引入了图中的独立半完全支配概念。如果集合??既是??的一个支配集，又是??的一个独立集，那么??被称为??的独立半完全支配集。用??????2?(??)表示??所有独立半完全支配集的集合。在[1]中证明了如果??是一个连通的非完全图，那么??????2?(??)≠0?。连通非完全图??的独立半完全支配数定义为?????2?(??)=min?{|??|:??∈??????2?(??)}。一个满足|??|=?????2?(??)的??集合被称为?????2?(??)集合。关于图中的独立半完全支配的更多结果可以在[1]、[14]、[15]中找到。根据定义，每个连通的非完全图??都满足?????2?(??)≤?????2?(??)。为了说明这些定义，考虑图1中所示的图??。左边的黑色顶点代表一个?????2?(??)集合，右边的代表一个?????2?(??)集合。

在[1]中，作者提出了关于图中的独立半完全支配的几个开放性问题。特别是，他们要求这个支配参数的新下界和上界，以及所有满足?????2?(??)=?????2?(??)的图的描述。在本文中，我们分别从树的视角解决了这两个问题。对于第一个问题，我们确定了当??是至少三阶的树时?????2?(??)的上界，并且当??是二叉树时给出了?????2?(??)的一个下界。最后，我们通过给出所有满足?????2?(??)=?????2?(??)的树的构造性描述来解决第二个开放性问题。树是一个连通且无环的图。树的叶子节点是度为1的节点。支撑节点是度至少为2且与叶子节点相邻的节点。半支撑节点是与支撑节点相邻但既不是叶子节点也不是支撑节点的节点。对于一棵树??，叶子节点、支撑节点和半支撑节点的集合分别用??(??)、???(??)和?????(??)表示。此外，我们用???(??)、???(??)和???(??)表示??的节点数、叶子节点数和支撑节点数，即???(??)=|???(??)|、???(??)=|??(??)|和???(??)=|???(??)|。如[6]所示，一棵有根树??有一个特殊的节点??，称为根节点。对于??中的每个非根节点??，??的父节点是??在唯一的(??,??)路径上的邻居，而??的子节点是??的任何其他邻居。??的后代节点是一个不同于??的节点，且唯一的?????路径包含??。因此，??的每个子节点都是??的后代节点。??的后代节点集合用???(??)表示，我们定义???[??]=???(??)∪{??}。以???[??]为根的最大子树是由???[??]诱导的??的子树，记为????。

（无根）二叉树是一个所有节点的度要么为1要么为3的树（例如，参见[6]、[16]）。因此，如果??有??1个度为1的节点和??3个度为3的节点，那么??1+3?=2?(???(??)?1)=2(???+????1)。所以，???=???+2且???(??)=2(???+1)，这意味着???(??)是偶数。图2中显示的树??1、???和???分别是四阶、六阶和八阶的唯一二叉树。通常，对于一个集合??????(??)，我们用?????表示去掉??中的所有节点及其相关边后得到的图。我们用????和???,???1分别表示阶数为??的路径图和星形图。树????,???1是通过将???,???1中的每条边恰好细分一次得到的。另外，???,?表示通过将???,?中的一条边恰好细分一次得到的双重星形图。

限制????32(??)的值：我们从一个有用的引理开始本节。给定一棵树??，将路径????附加到??2(??)中的一个顶点??意味着添加路径????并通过一条边将??与????的一个叶子节点连接起来。当??=1时，???中的单个非叶子节点直接与??连接。

引理2.1：对于任何阶数≥?的树??′，以下陈述成立：
(i) 如果??是通过将路径???附加到??2(??′)中的任何顶点??得到的，那么????32(??)≤????32(??′)+1。
(ii) 如果??是通过将路径???附加到??2(??′)中的任何顶点??得到的，那么...

具有????32(??)=????32(??)的树：为了描述独立半完全支配数等于半完全支配数的树，我们首先需要引入一些必要的定义。

定义3.1 [2]：相对于顶点??的树的几乎半完全支配集（ASTDS of ?? relative to ??）是一个支配集??（其|??|≥2），其中?????2[??]中的每个顶点都与其他某个??中的顶点的距离不超过2。相对于顶点??的树的几乎半完全支配数记为????32(??,??)，它是所有这样的支配集中最小的基数。