禁用两个子图的图的成对控制数
Paired Domination Number of Graphs with Two Forbidden Subgraphs
杨树承 1胡夫涛 1张昶旭1
作者信息
- 1. 安徽大学数学科学学院,合肥 230601
- 折叠
摘要
禁用子图条件下图参数的界是图论研究的重要内容.主要应用组合结构分析方法研究禁用两个子图的成对控制数.设D是V的非空子集,如果不在D的点一定与D中的某个点相邻,则称D为G的控制集.如果不含孤立点图G的控制集的导出子图包含完美匹配,则D称为G的成对控制集.最小成对控制集包含顶点的数目称为成对控制数.文章主要给出了当G是n阶连通的无爪和无埃菲尔图时成对控制数紧的上界.本文结果丰富了图的成对控制数的研究.
Abstract
The bound of graph parameters under the condition of forbidden subgraphs is an important part of graph theory research.Let D be a subset of V.If every vertex not in D is adjacent to a vertex in D,then D is a dominating set of G.If a dominating set D of a graph G without isolated vertices con-tains a perfect matching,then D is a paired dominating set of G.The paired domination number of G,is the minimum cardinality of all paired dominating sets.In this paper,we show a tight bound for a connected Claw-free and Eiffel-free graph G with order n.The results of this paper enrich the study of pairwise control domination numbers of graphs.
关键词
成对控制数/全控制数/爪图/埃菲尔图/禁用子图Key words
paired domination number/total domination number/claw graph/eiffel graph/forbidden subgraph引用本文复制引用
基金项目
国家自然科学基金项目(11401004)
安徽省自然科学基金(2108085MA02)
安徽省高校自然科学基金项目(KJ2020A0001)
出版年
2024
NETL
NSTL
万方数据