Characterization of graphs using domination polynomials

DOI10.1016/J.EJC.2010.03.007MaRDI QIDQ709243zbMATH OpenOpenAlexFDO

Authors S. Akbari, Saeid Alikhani, Y. H. Peng

Publication date 18 October 2010

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Abstract: Let G be a simple graph of order n. The domination polynomial of G is the polynomial D(G,x)=sum_{i=gamma(G)}^{n} d(G,i) x^{i}, where d(G,i) is the number of dominating sets of G of size i, and gamma(G) is the domination number of G. In this paper we study the domination polynomials of cubic graphs of order 10. As a consequence, we show that the Petersen graph is determined uniquely by its domination polynomial.

Recommendations

• On the \(\mathcal D\)-equivalence class of graph
• On the graphs with four distinct domination roots
• On the roots of domination polynomial of graphs
• On \(\mathcal D\)-equivalence class of complete bipartite graphs.
• On the zeros of domination polynomial of a graph

Cites work

• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• Dominating sets and domination polynomials of paths
• Domination-balanced graphs
• Introduction to domination polynomial of a graph.
• On the corona of two graphs

Cited in

(60)

• Strong Domination number of Hajós sum and vertex-sum of two graphs
• Domination polynomial of the rook graph
• On the semitotal dominating sets of graphs
• scientific article; zbMATH DE number 7671000 (Why is no real title available?)
• Domination polynomials of the grid, the cylinder, the torus, and the king graph
• On the number of isolate dominating sets of certain graphs
• On D-equivalence classes of some graphs
• Graphs whose certain polynomials have few distinct roots
• Domination polynomials of \(k\)-tree related graphs
• Some families of graphs with no nonzero real domination roots
• Neighborhood and domination polynomials of graphs
• The zero forcing polynomial of a graph
• Graph operations and neighborhood polynomials
• On the domination polynomial of a digraph: a generation function approach
• scientific article; zbMATH DE number 6116807 (Why is no real title available?)
• The average order of dominating sets of a graph
• On the \(\mathcal D\)-equivalence class of graph
• The Domination Equivalence Classes of Paths
• Distinctive power of the alliance polynomial for regular graphs
• On the independent domination polynomial of a graph
• On the eccentric connectivity polynomial of \(\mathcal{F}\)-sum of connected graphs
• The number of 2-dominating sets, and 2-domination polynomial of a graph
• Note on the subgraph component polynomial
• scientific article; zbMATH DE number 7527867 (Why is no real title available?)
• Domination Polynomials of certain hexagon lattice graphs
• Optimal domination polynomials
• On the number of perfect matchings of generalized theta graphs and the edge cover polynomials of friendship graphs
• Domination polynomial of clique cover product of graphs
• Independence equivalence classes of cycles
• The domination polynomial of a graph at \(-1\)
• Algebraic integers as chromatic and domination roots
• On the domination polynomial of some graph operations
• On the roots of total domination polynomial of graphs
• Perfect domination polynomial of homogeneous caterpillar graphs and of full binary trees
• On the average order of a dominating set of a forest
• The average domination polynomial of graphs is unimodal
• Complete \(r\)-partite graphs determined by their domination polynomial
• Computing the strong alliance polynomial of a graph
• On the roots of total domination polynomial of graphs. II
• On the number of fair dominating sets of graphs
• scientific article; zbMATH DE number 5812576 (Why is no real title available?)
• On the roots of domination polynomials
• Subset-sum representations of domination polynomials
• scientific article; zbMATH DE number 6423767 (Why is no real title available?)
• Connected domination polynomial of graphs
• On some parameters related to fixing sets in graphs
• Dominating sets and domination polynomials of certain graphs. II
• scientific article; zbMATH DE number 6403696 (Why is no real title available?)
• On \(\mathcal D\)-equivalence class of complete bipartite graphs.
• A characterization of network representable polymatroids
• More on the unimodality of domination polynomial of a graph
• On the domination polynomials of friendship graphs
• On the differential polynomial of a graph
• Alliance polynomial of regular graphs
• On the roots of domination polynomial of graphs
• On the graphs with four distinct domination roots
• Restrained domination polynomial of join and corona of graphs
• On the location of roots of graph polynomials
• Construction of dominating sets of certain graphs
• On the doubly connected domination polynomial of a graph

This page was built for publication: Characterization of graphs using domination polynomials

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