Dominating sets and domination polynomials of paths

DOI10.1155/2009/542040MaRDI QIDQ1028883zbMATH OpenOpenAlexWikidataFDO

Authors Saeid Alikhani, Y. H. Peng

Publication date 9 July 2009

Published in International Journal of Mathematics and Mathematical Sciences (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/0905.3268, https://eudml.org/doc/45521

zbMATH Keywords

dominating setrecursive formuladomination polynomial of paths

Mathematics Subject Classification ID

Graph polynomials (05C31) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Paths and cycles (05C38)

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.

Recommendations

• Construction of dominating sets of certain graphs
• The Domination Equivalence Classes of Paths
• Dominating sets and domination polynomials of certain graphs. II
• Dominating sets of centipedes
• Cycles are determined by their domination polynomials.

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2141600 (Why is no real title available?)
• Introduction to domination polynomial of a graph.
• Paired-domination in graphs

Cited in

(32)

• scientific article; zbMATH DE number 6921365 (Why is no real title available?)
• Dominating sets and domination polynomials of certain graphs. II
• Domination Polynomials of certain hexagon lattice graphs
• Recurrence relations and splitting formulas for the domination polynomial
• On the graphs with four distinct domination roots
• Perfect domination polynomial of homogeneous caterpillar graphs and of full binary trees
• scientific article; zbMATH DE number 1933232 (Why is no real title available?)
• Characterization of graphs using domination polynomials
• Optimal domination polynomials
• scientific article; zbMATH DE number 7587190 (Why is no real title available?)
• Algebraic integers as chromatic and domination roots
• Construction of dominating sets of certain graphs
• Cycles are determined by their domination polynomials.
• On coefficients of edge domination polynomial of a graph
• Subset-sum representations of domination polynomials
• scientific article; zbMATH DE number 7671000 (Why is no real title available?)
• Graphs whose certain polynomials have few distinct roots
• Complete r-partite graphs determined by their domination polynomial
• Domination polynomials of the grid, the cylinder, the torus, and the king graph
• Dominating sets of centipedes
• Connected domination polynomial of graphs
• THE NUMBER OF CC-DOMINATING SETS OF SOME GRAPHS
• On the number of isolate dominating sets of certain graphs
• New network entropy : The domination entropy of graphs
• On total edge fixed geodomination sets and polynomials of paths
• Paths on polymatroids
• On the location of roots of graph polynomials
• On the domination polynomial of some graph operations
• A study of mixed tree domination polynomials in some class of graphs
• The domination polynomial of a graph at -1
• On the dominating set polytope
• The Domination Equivalence Classes of Paths

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)