禁用两个子图的图的全控制数  

Total 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年第1期93-97,106,共6页Journal of Harbin University of Commerce：Natural Sciences Edition

基　　金：国家自然科学基金(11401004);安徽省自然科学基金(2108085MA02);安徽省高校自然科学基金(KJ2020A0001)。

摘　　要：设G=V(V,E)是一个简单无向图.一个点悬挂三个一度点的图称为爪图,D图是一个三角形其中两个点各悬挂一条长为2的路.如果图G的任何导出子图都不同构于爪图也不同构于D图,则称G为无爪和无D图.设S是V的非空子集,如果不在S的点一定与S中的某个点相邻,则称S为G的控制集.如果G中的点一定与S中的某个点相邻,则S称为G的全控制集.最小全控制集包含顶点的数目称为全控制数.给出了当G是N阶连通的无爪和无D图时全控制数紧的上界.Let G=(V,E)be a simple undirected graph.A claw graph was one vertex pending three degree one vertex,A D graph was a triangle with two vertices that each of them pending a path of length 2.If any induced subgraph of G does not isomorphic to claw graph and not isomorphic to D graph,G was claw-free and D graph.Let S be a subset of V.If every vertex not in S was adjacent to a vertex in S,then S was a dominating set of G.If every vertex in G was adjacent to a vertex in S,then S was a total dominating set of G.The total domination number of G,was the minimum cardinality of all total dominating sets.In this paper,a tight bound for a connected claw-free and D-freegraph G withorder n were shown.

关 键 词：控制数 控制集 全控制数 爪图 D图 禁用子图 

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