基于分合链方法的图的意大利支配数研究  

The Italian Domination Number of Graphs Based on Decomposition and Combination Chain Method

作　　者：高红 郭媛媛 刘行 Gao Hong;Guo Yuan-yuan;Liu Xing(College of Science,Dalian Maritime University,Dalian 116026,China)

机构地区：[1]大连海事大学理学院,辽宁大连116026

出　　处：《广东工业大学学报》2023年第2期1-4,共4页Journal of Guangdong University of Technology

基　　金：中国学位与研究生教育学会学位与研究生教育研究课题(2020MSA43);大连海事大学研究生教改项目(YJG2022607)。

摘　　要：图的支配问题是图论的重要内容。根据实际应用背景的不同,衍生出了很多种不同的支配类型。意大利支配是一种新兴的支配类型。确定图的意大利支配数是多项式复杂程度的非确定性问题(即NP困难问题)。本文利用可拓学中分合链方法,证明了图的意大利支配数下界与上界相等,从而确定出图的意大利支配数。该方法可移植性好,可用于确定多种图形的不同支配数。Domination on graphs is an important part in Graph Theory.According to different practical application backgrounds,many kinds of domination are presented.Italian domination is a new kind of domination on graphs.To determine the Italian domination number of a graph is a non-deterministic polynomial problem(i.e.NP-hard problem).In this research,the decomposition and combination chain method in extenics is used to prove that the lower bound of the Italian domination number of a graph is equal to the upper bound,so that the Italian domination number can be determined.The method has good portability and can be used to determine different domination numbers of various graphs.

关 键 词：图论 图的支配数 可拓学 分合链 物元 

分 类 号：O157.5[理学—数学] G642.4[理学—基础数学]