Subset-sum representations of domination polynomials

DOI10.1007/S00373-013-1286-ZMaRDI QIDQ2014717zbMATH OpenOpenAlexFDO

Authors Tomer Kotek, James Preen, Peter Tittmann

Publication date 16 June 2014

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

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

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)

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.

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

Cites work

• Characterization of graphs using domination polynomials
• Dominating sets and domination polynomials of certain graphs. II
• Dominating sets and domination polynomials of paths
• Domination reliability
• Mean value for the matching and dominating polynomial
• On the zeros of domination polynomial of a graph
• 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)