Dominating sets and domination polynomials of paths

DOI10.1155/2009/542040zbMATH Open1177.05081arXiv0905.3268OpenAlexW4214903404WikidataQ58648453 ScholiaQ58648453MaRDI QIDQ1028883FDOQ1028883

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)

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.

Full work available at URL: https://arxiv.org/abs/0905.3268

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.

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)

Cites Work

• Title not available (Why is that?)
• Introduction to domination polynomial of a graph.
• Paired-domination in graphs
• Title not available (Why is that?)

Cited In (32)

• Title not available (Why is that?)
• Domination Polynomials of certain hexagon lattice graphs
• Dominating sets and domination polynomials of certain graphs. II
• On the graphs with four distinct domination roots
• Recurrence relations and splitting formulas for the domination polynomial
• Perfect domination polynomial of homogeneous caterpillar graphs and of full binary trees
• Title not available (Why is that?)
• Characterization of graphs using domination polynomials
• Title not available (Why is that?)
• Optimal domination polynomials
• 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
• Title not available (Why is that?)
• 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
• THE NUMBER OF CC-DOMINATING SETS OF SOME GRAPHS
• Connected domination polynomial of graphs
• On the number of isolate dominating sets of certain graphs
• On total edge fixed geodomination sets and polynomials of paths
• New network entropy : The domination entropy of graphs
• 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
• On the dominating set polytope
• The Domination Equivalence Classes of Paths
• The domination polynomial of a graph at \(-1\)

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)