禁用两个子图的图的成对控制数  

Paired Domination Number of Graphs with Two Forbidden Subgraphs

作　　者：杨树承 胡夫涛[1] 张昶旭 YANG Shucheng;HU Futao;ZHANG Changxu(School of Mathematical Sciences,Anhui University,Hefei 230601,China)

机构地区：[1]安徽大学数学科学学院,合肥230601

出　　处：《合肥学院学报（综合版）》2024年第2期10-14,共5页Journal of Hefei University：Comprehensive ED

基　　金：国家自然科学基金项目“图的控制约束问题研究”(11401004);安徽省自然科学基金“图的控制及相关问题研究”(2108085MA02);安徽省高校自然科学基金项目“基于电阻距离的图结构分析”(KJ2020A0001)。

摘　　要：禁用子图条件下图参数的界是图论研究的重要内容。主要应用组合结构分析方法研究禁用两个子图的成对控制数。设D是V的非空子集,如果不在D的点一定与D中的某个点相邻,则称D为G的控制集。如果不含孤立点图G的控制集的导出子图包含完美匹配,则D称为G的成对控制集。最小成对控制集包含顶点的数目称为成对控制数。文章主要给出了当G是n阶连通的无爪和无埃菲尔图时成对控制数紧的上界。本文结果丰富了图的成对控制数的研究。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.

关 键 词：成对控制数 全控制数 爪图 埃菲尔图 禁用子图 

分 类 号：O157.5[理学—数学]