不含B_1,1的无爪图的安全支配数

The Secure Domination Number of{B_1,1, Claw}-Free Graphs

摘要: 设集合S为图G的一个支配集，若对于V (G) − S中任意一点u，其在S中均存在邻点v，使得 (S − {v}) ∪ {u}是G的支配集，则称S是G的一个安全支配集。 在G的所有安全支配集中，基数最 小的安全支配集称为G的最小安全支配集，其基数称为G的安全支配数，记作γs(G)。 本文聚焦不 含公牛图B_1,1的无爪图，研究其安全支配数的上界。 证明了若G是独立数至少为3的不含B_1,1的无 爪图，则其安全支配数的上界为G 的独立数，并给出例图表明该上界是紧的。

Abstract: Let S be a dominating set of a graph G. If for every vertex u ∈ V (G) − S, there exists a neighbor v of u in S such that (S − {v}) ∪ {u} is a dominating set of G, then S is called a secure dominating set of G. The secure domination number of G, denoted by γs(G),is the minimum cardinality of a secure dominating set in G. This paper focuses on the upper bound problem of the secure domination number in {B_1,1, claw}-free graphs, where B1,1 denotes the bull graph. We prove that if G is a {_1,1, claw}-free graph with independence number at least 3, then the upper bound of secure domination number is the independence number of G; moreover, we construct an example to show that this bound is tight.