| 高红,黄佳欢,尹亚男,杨元生.广义彼得森图意大利控制数[J].,2021,61(6):652-655 |
| 广义彼得森图意大利控制数 |
| Italian domination number of generalized Petersen graph |
| |
| DOI：10.7511/dllgxb202106013 |
| 中文关键词: 罗马控制数 意大利控制数 广义彼得森图 |
| 英文关键词: Roman domination number Italian domination number generalized Petersen graph |
| 基金项目:国家自然科学基金资助项目(62071079). |
|
| 摘要点击次数: 221 |
| 全文下载次数: 291 |
| 中文摘要: |
| 图的罗马控制来源于古罗马帝国的军事防御问题．图的意大利控制是一种泛化的罗马控制．确定图的意大利控制数是NP困难的．一般情况下，很难确定某一类图意大利控制数的精确值，只能给出其上界或下界．通过构造可递推的意大利控制函数，得到了广义彼得森图P(n，k)(k≥4)的意大利控制数紧的上界．结合前人给出的意大利控制数的下界，确定了当k≡2，3(mod 5)且n≡0(mod 5)时，P(n，k)(k≥4)意大利控制数的精确值． |
| 英文摘要: |
| Roman domination on a graph is originated from defending the Roman Empire. Italian domination is a generalization of Roman domination. To determine the Italian domination number of a graph is NP hard. For a certain class of graphs, usually only the upper or lower bound of the Italian domination number can be given, and it is difficult to determine the exact value of the Italian domination number. The sharp upper bounds on Italian domination numbers of generalized Petersen graph P(n,k)(k≥4)are calculated by constructing recursive Italian domination functions. Therefore, the exact value of the Italian domination number is determined forP(n,k)(k≥4) whenk≡2,3(mod 5)andn≡0(mod 5) together with the lower bound given by others. |
|
查看全文
查看/发表评论 下载PDF阅读器 |
| 关闭 |
|
|
|