Dominating sets and domination polynomials of paths (Q1028883): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 4 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W4214903404 / rank | |||
Normal rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q58648453 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 0905.3268 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Paired-domination in graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4198056 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Introduction to Domination Polynomial of a Graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4653767 / rank | |||
Normal rank |
Latest revision as of 18:00, 1 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Dominating sets and domination polynomials of paths |
scientific article |
Statements
Dominating sets and domination polynomials of paths (English)
0 references
9 July 2009
0 references
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.
0 references
dominating set
0 references
recursive formula
0 references
domination polynomial of paths
0 references