Source-linked AI summary
Introduction to Domination Polynomial of a Graph
Saeid Alikhani, Yee-hock Peng
TL;DR
The paper introduces a polynomial that counts a graph’s dominating sets by size and derives properties of it and its coefficients. It proves product and join formulas, studies unimodality, and establishes unimodality for the corona graph G ◦K1.
Problem
The paper addresses how to represent and study the numbers of dominating sets of each cardinality in a graph.
Method
The paper defines the domination polynomial and derives formulas and coefficient properties using graph constructions such as disjoint unions, joins, and coronas.
Results
The paper obtains domination-polynomial properties and proves that D(G ◦K1, x) is unimodal.
Takeaways & Limitations
Domination polynomials provide a framework for counting dominating sets by size and analyzing their coefficient sequences.
Abstract
from arXiv · showhide
We introduce a domination polynomial of a graph G. The domination polynomial of a graph G of order n is the polynomial D(G, x) =\sum_{i=1}^n d(G, i)x^i, where d(G, i) is the number of dominating sets of G of size i. We obtain some properties of D(G, x) and its coefficients. Also we compute this polynomial for some specific graphs.
1 Introduction
The paper establishes graph-neighborhood and domination terminology, then motivates and introduces the domination polynomial and studies its structural properties. It also highlights applications to corona graphs and unimodality.
- 1 Introduction: The introduction defines graph neighborhoods, dominating sets, the domination number γ(G), and γ-sets as foundational terminology.The open neighborhood of a vertex contains its adjacent vertices, while the closed neighborhood also includes the vertex itself.
- 1 Introduction: The domination polynomial counts dominating sets by cardinality, with coefficients forming the sequence studied throughout the paper.A dominating set covers every vertex through its closed neighborhood; d(G, i) counts such sets of size i.
- 1 Introduction: It also recalls the corona construction and graph join notation used for later graph operations.The corona combines one graph with copies of another, while the join adds all edges between the two vertex sets.
- 1 Introduction: The paper develops properties of the domination polynomial and its coefficients, including questions about coefficient unimodality.A polynomial is unimodal when its coefficient sequence is unimodal.
- 1 Introduction: The study includes domination polynomials for corona graphs, specifically G ◦K1, and establishes their unimodality.The corona G ◦K1 adds a pendant vertex and edge to each vertex of G.
2 Introduction to domination polynomial
The paper defines the domination polynomial by counting dominating sets by cardinality and derives structural formulas for disconnected graphs and graph joins. It then applies these results to complete graphs, complete bipartite graphs, stars, and wheels.
- Definition and examples: The domination polynomial D(G, x) encodes the number d(G, i) of dominating sets of each cardinality i.For P4, the polynomial is D(P4, x) = x4 + 4x3 + 4x2.
- Specific graphs: For complete graphs, every nonempty vertex subset dominates, giving D(Kn, x) = (1 + x)n −1.
- Disconnected graphs: For a graph with components G1, . . . , Gm, the domination polynomial factors as D(G, x) = D(G1, x) · · · D(Gm, x).
- Joins: The join formula expresses D(G1 ∨ G2, x) using the component polynomials and additional terms for dominating sets contained in either joined graph.The proof counts unions of dominating sets from both graphs and separately accounts for sets that dominate the join from one side.
- Specific graphs: The resulting formulas are D(Km,n, x) = ((1 + x)m −1)((1 + x)n −1) + xm + xn, D(K1,n, x) = xn + x(1 + x)n, and D(Wn, x) = x(1 + x)n−1 + D(Cn−1, x) for n ≥4.The wheel identity follows from Wn = Cn−1 ∨K1, while the star formula is the m = 1 case of the complete bipartite formula.
3 Coefficients of domination polynomial
This section establishes coefficient properties of the domination polynomial, including monotonicity, degree and root behavior, and structural information recoverable from its coefficients.
- 3 Coefficients of domination polynomial: The coefficient d(G, n) equals 1 for connected graphs, while d(G, n −1) equals n.
- 3 Coefficients of domination polynomial: The domination polynomial has no coefficients below the domination number, no constant term, and is strictly increasing on [0, ∞).Specifically, d(G, i) = 0 exactly when i < γ(G) or i > n, and zero is a root with multiplicity γ(G).
- 3 Coefficients of domination polynomial: The degree of D(G, x) is at least the degree of the domination polynomial of any induced subgraph H.
- 3 Coefficients of domination polynomial: The coefficients determine structural graph information, including isolated vertices, K2-components, and vertices of degree one.For example, the number r of isolated vertices satisfies r = n − d(G, n −1).
- 3 Coefficients of domination polynomial: d(G, i) ≤ d(G, i + 1) for every 0 ≤ i < n, so domination-polynomial coefficients are nondecreasing.The proof constructs a matching from dominating i-sets to containing (i + 1)-sets using Hall’s theorem.
- 3 Coefficients of domination polynomial: The paper conjectures that the domination polynomial of every graph is unimodal.The coefficient monotonicity result is presented as useful for studying this conjecture.
4 Domination polynomial of G ◦K1
This section analyzes domination polynomials of corona graphs G ◦ K1, deriving their coefficients and proving unimodality through coefficient patterns and root properties.
- 4 Domination polynomial of G ◦K1: D(G ◦ K1, x) is unimodal for every graph G of order n.The paper also notes that, except for zero, this polynomial has only negative real roots, implying log-concavity and hence unimodality.
- 4 Domination polynomial of G ◦K1: The domination number of G ◦ K1 is n, so d(G ◦ K1, m) = 0 for m < n.Every original-leaf pair requires at least one selected vertex, while the n pendant vertices form a dominating set.
- 4 Domination polynomial of G ◦K1: For n ≤ m ≤ 2n, the paper derives d(G ◦ K1, m) by selecting both vertices in some pendant pairs and one vertex in every remaining pair.The counting argument separates the number of pairs contributing two selected vertices from those contributing one.
- 4 Domination polynomial of G ◦K1: For graphs of orders 3n, 3n + 1, and 3n + 2, coefficients increase to a central range and then decrease.The order-3n+2 family has equal central coefficients, while the other displayed families have strict central transitions.
- 4 Domination polynomial of G ◦K1: The mode is unique for the families {D(G∗ 3n, x)} and {D(G∗ 3n+1, x)}, but not unique for {D(G∗ 3n+2, x)}.