On roots of domination polynomials for friendship and book graphs

Bilal Ahmad Rather · 2026

Read On roots of domination polynomials for friendship and book graphs by Bilal Ahmad Rather (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-08998.txt.

Introduction

Rather studies domination polynomials of friendship and book graphs, taking up questions left open by earlier work. For friendship graphs with even size, the polynomial has exactly three real zeros. They are zero and two simple zeros in the intervals minus two to minus one and minus one to zero. The paper also bounds root size explicitly. For book graphs it determines the full limit set of roots and parity-dependent facts about real roots. Neither family has a nonzero integer root, while corona families admit only minus two.

Catalog record

CREATORBilal Ahmad Rather
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE38255
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.08998

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On roots of domination polynomials for friendship and book graphs Bilal Ahmad Rather Abstract This study examines the domination polynomials of friendship graphs and book graphs, focusing on unanswered questions related to these families [Alikhani, Brown and Jahari, on the domination polynomials of friendship graphs, Filomat 30 (1) (2016) 169–178]. For the friendship graph F n F_{n} , with even n n , we show that the polynomial D ⁡ ( F n , x ) D(F_{n},x) has exactly three real zeros: 0 0 and two simple zeros in the intervals ( − 2 , − 1 ) (-2,-1) and ( − 1 , 0 ) (-1,0) . We further show that these two nonzero zeros have monotonic variation and converge to − 1 − 1 2 -1-\frac{1}{\sqrt{2}} and − 1 + 1 2 -1+\frac{1}{\sqrt{2}} , respectively. We obtain the quantitative approximation ( | z | − 1 ) 2 ​ log ⁡ | z | ≤ n (|z|-1)^{2}\log|z|\leq n for any complex zeros of D ⁡ ( F n , x ) D(F_{n},x) , resulting in the explicit bound | z | ≤ 1 + n log ⁡ 2 |z|\leq 1+\sqrt{\tfrac{n}{\log 2}} . For book graphs B n B_{n} , we ascertain the comprehensive limit set of domination roots and establish results about the presence of real roots contingent on parity. We provide a partial answer to the integer-root an issue by establishing that friendship and book graphs have no nonzero integer domination roots, whereas for corona families, the only nonzero integer root is − 2 -2 . 2020 Mathematics Subject Classification. Primary 05C69; Secondary 05C31, 30C15. Keywords. domination polynomial; domination root; friendship graph; book graph; limit of zeros. 1 Introduction Let G=(V,E) be a finite simple graph. A subset S\subseteq V is called a dominating set if every vertex of V\setminus S has a neighbor in S . The domination polynomial of G is the generating function of domination sets, and is defined as D(G,x)=\sum_{i=\gamma(G)}^{|V|}d(G,i)x^{i}, where d(G,i) denotes the number of dominating sets of size i and \gamma(G) is the domination number of G . Domination theory is a well-established component of graph theory, driven by robust structural and algorithmic considerations, encompassing resource allocation, coverage, and network resilience issues; key references are [ 17 , 5 ] . From an algebraic perspective, domination polynomials encapsulate a significant amount of combinatorial information within a singular entity, and their zeros frequently reveals underlying regularity in the examined graph family. This philosophy is already recognized from independence, matching, and chromatic polynomials, where the positioning of zeros has resulted in both structural theorems and asymptotic phenomena [ 10 , 11 , 12 , 14 , 13 ] . The interest in dominance roots has increased due to the combinatorial richness and computational complexity of dominating sets. Generally, ascertaining whether \gamma(G)\leq k is NP-complete [ 16 ] , hence precise formulations for D(G,x) are seldom and much sought after. Numerous graph classes are recognized as being defined by their domination polynomial, although others are not; refer to [ 1 , 6 , 8 , 19 , 23 ] . The interest in dominance roots has increased significantly owing to the combinatorial intricacy and computing complexity of dominating sets. Determining whether \gamma(G)\leq k is NP-complete [ 16 ] , hence exact formulations for D(G,x) are rare and much desired. Several graph classes are identified by their domination polynomial, whereas others are not, see [ 1 , 6 , 8 , 22 , 21 , 24 ] . Among the most natural triangle-rich families are the friendship graphs F_{n}=K_{1}+nK_{2} and the n -book graphs B_{n} , obtained by identifying a common edge in n copies of C_{4} . The friendship graphs are defined by the Erdős–Rényi–Sós friendship theorem [ 15 ] , establishing them as a standard test family for extremal and algebraic inquiries. In a seminal paper, Alikhani, Brown, and Jahari [ 7 ] formulated explicit equations for the domination polynomials of F_{n} and B_{n} , examined their root configurations, demonstrated a limiting hyperbola for the roots of F_{n} , confirmed that F_{n} is not D -unique for n\geq 3 , and presented multiple unresolved questions regarding precise real-root counts, modulus constraints, book-graph root topology, and integer domination roots. The hypothesis presented in [ 7 ] was subsequently advanced in [ 20 , 3 , 4 ] . This study addresses these unresolved inquiries. Specifically, we reexamine Questions 3.1, 3.2, 3.3, and 3.6 (see Open Problem 2.6 ) from [ 7 ] . The initial principal theorem provides a definitive resolution to Question 3.1: when n is even, D(F_{n},x) possesses precisely three real zeros. The demonstration is not a numerical argument; it relies on a rigorous monotonicity analysis of two logarithmic equations derived by moving the variable by 1 . We subsequently refine the asymptotic analysis by demonstrating the monotone convergence of the two nonzero real roots to the hyperbola intercepts already indicated in [ 7 ] . In Question 3.2, we formulate a novel quantitative assessment for all complex zeros of D(F_{n},x) , specifically (|z|-1)^{2}\log|z|\leq n, which immediately implies the explicit sublinear bound |z|\leq 1+\sqrt{\frac{n}{\log 2}}. This provides a definitive, verified the upper bound on the modulus, significantly more precise than rudimentary coefficient bounds. Our examination of book graphs offers a limited yet thorough response to Question 3.3. Employing the results from [ 9 , 12 ] , we ascertain the comprehensive limiting set of domination roots of B_{n} as a union of three algebraic components along with two distinct points. We also establish parity-dependent existence assertions for the real roots of D(B_{n},x) and define the exact intersections with the real axis of the limit set. Ultimately, inspired by Question 3.6, we demonstrate that friendship graphs and book graphs lack nonzero integer domination roots. In conjunction with the corona constructions from [ 7 ] , this provides a partial affirmative response to the overarching integer-root problem: across the natural families examined, the only nonzero integer domination root that emerges is -2 . The results are intresting in two specific respects. Initially, they resolve a previously unresolved precise enumeration issue concerning the real roots of friendship graphs. Secondly, they transform the qualitative root plots of [ 7 ] into quantitative theorems: precise root counts, monotonic convergence, a sublinear modulus bound, and limit characterization for the zeros of book graphs. The combination of analytic inequalities, recurrence-free algebraic transformations, and asymptotic root-limit techniques is particularly efficacious for domination polynomials of dense graph families exhibiting repetitive local structures. The article is organized as: Section 2 compiles the notation, fundamental identities, and established results utilized throughout the article. Section 3 provides a comprehensive resolution to Question 3.1 [ 7 ] by demonstrating that even friendship graphs possess precisely three real domination roots and by accurately identifying their two nonzero roots. Section 4 addresses Question 3.2 [ 7 ] by formulating a novel global modulus estimate for the complex roots of D(F_{n},x) and providing a clear sublinear upper bound. Section 5 addresses Question 3.3 [ 7 ] : we ascertain the limit set for the roots of the book graphs and infer multiple implications regarding real roots. Section 6 pertains to Question 3.6 [ 7 ] . We show

Read the complete text