Subset-sum representations of domination polynomials

DOI10.1007/S00373-013-1286-ZzbMATH Open1291.05094arXiv1207.2430OpenAlexW1975155259MaRDI QIDQ2014717FDOQ2014717

Authors: Tomer Kotek, James Preen, Peter Tittmann 

Publication date: 16 June 2014

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: The domination polynomial D(G,x) is the ordinary generating function for the dominating sets of an undirected graph G=(V,E) with respect to their cardinality. We consider in this paper representations of D(G,x) as a sum over subsets of the edge and vertex set of G. One of our main results is a representation of D(G,x) as a sum ranging over spanning bipartite subgraphs of G. We call a graph G conformal if all of its components are of even order. We show that the number of dominating sets of G equals a sum ranging over vertex-induced conformal subgraphs of G.

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

Recommendations

• Introduction to domination polynomial of a graph.
• Dominating sets and domination polynomials of certain graphs. II
• scientific article; zbMATH DE number 6423767
• On the domination polynomial of a digraph: a generation function approach
• Neighborhood and domination polynomials of graphs

zbMATH Keywords

graph polynomialdominating setdomination polynomial

Mathematics Subject Classification ID

Graph polynomials (05C31) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Enumeration in graph theory (05C30)

Cites Work

• On the zeros of domination polynomial of a graph
• Domination reliability
• Mean value for the matching and dominating polynomial
• Characterization of graphs using domination polynomials
• Dominating sets and domination polynomials of paths
• Dominating sets and domination polynomials of certain graphs. II
• The domination polynomial of a graph at \(-1\)

Cited In (6)

• On the roots of domination polynomial of graphs
• The average domination polynomial of graphs is unimodal
• Recurrence relations and splitting formulas for the domination polynomial
• Neighborhood and domination polynomials of graphs
• Graph operations and neighborhood polynomials
• Bipartition polynomials, the Ising model, and domination in graphs

This page was built for publication: Subset-sum representations of domination polynomials

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