Characterization of graphs using domination polynomials

DOI10.1016/J.EJC.2010.03.007zbMATH Open1207.05092arXiv0905.3281OpenAlexW2090731186MaRDI QIDQ709243FDOQ709243

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

Publication date: 18 October 2010

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

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• On the corona of two graphs
• Domination-balanced graphs
• Introduction to Domination Polynomial of a Graph
• Dominating sets and domination polynomials of paths

Cited In (56)

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

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)