Twain Secure Perfect Dominating Sets and Twain Secure Perfect Domination Polynomials of Centipedes

Abstract

Let ???? = (????,????) be a simple graph. A set ???? ⊆ ???? is a dominating set of ????, if every vertex in ???? \???? is adjacent to at least one vertex in ????. A subset ???? of ???? is called a twain secure perfect dominating set of ???? (TSPD-set) if every vertex ???? ∈ ???? \???? is adjacent to exactly one vertex ???? ∈ ???? and (????\{????}) ∪ {????} is a dominating set of ????. The twain secure perfect domination number of ????, represented as ????????????????(????), is the lowest cardinality of a twain secure perfect dominating set of ????. The centipede with 2???? vertices is represented by ????????∗, and the family of all twain secure perfect dominating sets of ????????∗ with cardinality ???? is represented by ????????????????(????????∗ ,????). Let ????????????????(????????∗ ,????)=|????????????????(????????∗ ,????)|. This article builds ????????????????(????????∗ ,????) and derives a recursive formula for ????????????????(????????∗ ,????). With this recursive formula, we examine the polynomial ????????????????(????????∗ ,????)=Σ????????????????(????????∗ ,????)2????????=???????????? which we call the twain secure perfect domination polynomial of centipedes. To create all twain secure perfect dominating sets of centipedes and twain secure perfect domination polynomials of centipedes, we employ a recursive approach in this study.