一类仙人掌图的意大利支配问题

Italian Domination Problem in a Class of Cactus Graphs

摘要: 意大利支配问题是图论中经典支配属的一个变体。图$G$ 的一个意大利支配函数，是函数$f:V\to \left\{0,1,2\right\}$ ，满足对任意$f\left(v\right)=0$ 的顶点$v\in V$ ，有${\displaystyle {\sum }_{u\in N\left(v\right)}f\left(u\right)}\ge 2$ 。图$G$ 的一个意大利支配函数的权重之和为$f\left(V\right)={\displaystyle {\sum }_{u\in V}f\left(u\right)}$ ，意大利支配数${\gamma }_I\left(G\right)$ 是一个意大利函数的最小权。本文针对等距m-仙人掌链的意大利支配问题，给出了其意大利数的计算公式。对于任意m-仙人掌链，给出了其意大利支配数的上界与下界，且发现了该类图一系列具有极值特性的链结构。

Abstract: The Italian domination problem is a variant of the classical domination property in graph theory. An Italian dominating function of a graph $G$ is a function $f:V\to \left\{0,1,2\right\}$ such that for every vertex $v\in V$ with $f\left(v\right)=0$ , the condition ${\displaystyle {\sum }_{u\in N\left(v\right)}f\left(u\right)}\ge 2$ holds. The weight of an Italian dominating function of $G$ is defined as $f\left(V\right)={\displaystyle {\sum }_{u\in V}f\left(u\right)}$ , and the Italian domination number ${\gamma }_I\left(G\right)$ is the minimum weight among all Italian dominating functions. This paper addresses the Italian domination problem for isometric m-cactus chains. We establish an exact formula for the Italian domination number of such chains. For arbitrary m-cactus chains, we derive both upper and lower bounds for their Italian domination number. Furthermore, we identify a family of chain structures within this graph class that exhibit extremal properties.