Dominating sets and domination polynomials of paths

Abstract: Let G=(V,E) be a simple graph. A set Ssubset V is a dominating set of G, if every vertex in VS is adjacent to at least one vertex in S. Let {mathcal C}_n^i be the family of dominating sets of a cycle C_n with cardinality i, and let d(C_n,i) = |{mathcal C}_n^i. In this paper, we construct {mathcal C}_n^i, and obtain a recursive formula for d(C_n, i). Using this recursive formula, we consider the polynomial D(C_n, x) = sum_{i=1}^n d(C_n, i)x^i, which we call domination polynomial of cycles and obtain some properties of this polynomial.

Review text

Summary: Let \(G=(V,E)\) be a simple graph. A set \(S\subseteq V\) is a dominating set of \(G\), if every vertex in \(V\setminus S\) is adjacent to at least one vertex in \(S\). Let \(\mathcal P_{n}^{i}\) be the family of all dominating sets of a path \(P_{n}\) with cardinality \(i\), and let \(d(P_{n},j)=|\mathcal P_{n}^{j}|\). In this paper, we construct \(\mathcal P_{n}^{i}\), and obtain a recursive formula for \(d(P_{n},i)\). Using this recursive formula, we consider the polynomial \(D(P_{n},x)=\sum_{i=\lceil n/3\rceil}^{n}\, d(P_{n},i)x^{i}\), which we call domination polynomial of paths and obtain some properties of this polynomial.

Recommendations

Cites work

Cited in

(36)

This page was built for publication: Dominating sets and domination polynomials of paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1028883)