Domination polynomial is unimodal for large graphs with a universal vertex

2021/11/01 by Shengtong Zhang, Zhang, Shengtong
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2111.00641

openalex publication_date 2021/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For a undirected simple graph G, let d_i(G) be the number of i-element dominating vertex set of G. The domination polynomial of the graph G is defined as D(G, x) = ∑_{i = 1}ⁿ d_i(G)xⁱ. Alikhani and Peng conjectured that D(G, x) is unimodal for any graph G. Answering a proposal of Beaton and Brown, we show that D(G, x) is unimodal when G has at least 2¹³ vertices and has a universal vertex, which is a vertex adjacent to any other vertex of G. We further determine possible locations of the mode.

Related

• On the Unimodality of Domination Polynomials
• Unimodality and monotonic portions of certain domination polynomials
• Some families of graphs whose domination polynomials are unimodal
• On the unimodality of nearly well-dominated trees
• The domination polynomial of powers of paths and cycles