🔢 mathematics

Independent domination polynomial of comaximal graphs of commutative rings

This paper investigates the independent domination and independence polynomials of the comaximal graph of the ring of integers modulo $n$ , $\Gamma(\mathbb{Z}_n)$ , by deriving explicit formulas for specific cases, establishing bounds for their zeros, and analyzing their unimodal and log-concave properties.

Original authors: Bilal Ahmad Rather

Published 2026-04-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Bilal Ahmad Rather

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant, bustling city called Ring City. In this city, every building is a number, and the streets connecting them follow very specific rules based on how those numbers interact.

This paper is like a detective story where the author, Bilal Ahmad Rather, tries to map out the hidden social structures of this city to solve two specific puzzles:

The "Guard" Puzzle: How can we place the fewest number of guards on the buildings so that every building is either guarded or next to a guarded one, without any two guards being neighbors?
The "Party" Puzzle: What is the largest group of people we can invite to a party where no two guests know each other?

Here is the breakdown of the paper using simple analogies.

1. The City Map: The Comaximal Graph

First, the author defines the city layout.

The Buildings (Vertices): Every number in the ring (like the numbers 0, 1, 2... up to $n-1$ ) is a building.
The Streets (Edges): Two buildings are connected by a street if they are "comaximal." In math-speak, this means if you combine their "neighborhoods," you can reach every other building in the city.
- Analogy: Imagine two people are friends if, when they pool their resources, they can buy the whole city. If they can, they get a direct phone line (an edge).

2. Puzzle A: The Independent Domination Polynomial (The Guard Problem)

The author is interested in Independent Dominating Sets.

Dominating Set: A group of guards such that every building in the city is either a guard or next to a guard.
Independent: No two guards are standing next to each other (they can't chat; they must be isolated from each other).
The Polynomial: This is a mathematical "scorecard." It counts how many different ways you can arrange these guards for every possible group size.
- Example: If you have 5 ways to put 1 guard, 3 ways to put 2 guards, and 1 way to put 3 guards, the polynomial looks like $5x + 3x^2 + 1x^3$ .

What the paper found:
The author figured out exactly how to calculate this scorecard for cities built from specific types of numbers (like prime numbers or products of primes).

The "Shape" of the Scorecard: The author checked if the numbers in the scorecard go up and then down smoothly (like a hill). This is called being Unimodal.
The "Smoothness" Check: He also checked if the numbers are "log-concave" (a fancy way of saying the hill doesn't have weird bumps or dips).
The Result: For many specific city types (like those built from one or two prime numbers), the scorecard forms a perfect, smooth hill. But for more complex cities, the hill might get bumpy or have missing steps.

3. Puzzle B: The Independence Polynomial (The Party Problem)

This is a slightly different puzzle. Here, we just want the biggest possible party where no one knows anyone else.

The Polynomial: This counts how many different "no-neighbor" parties of size 1, size 2, size 3, etc., can be formed.

What the paper found:

The author derived formulas for these party counts for specific city types.
The "Zero" Hunt: Every polynomial has "roots" (zeros). If you plug a number into the formula and get zero, that number is a root.
- Analogy: Imagine the polynomial is a rollercoaster. The "zeros" are the points where the track touches the ground.
The author used a famous math rule (the Eneström-Kakeya theorem) to predict where these "ground-touching" points would be.
The Pattern: When he plotted these zeros on a graph, they didn't scatter randomly. They formed beautiful, curved patterns, often hugging the edge of a circle or a specific shape on the negative side of the graph. It's like finding that all the "ghosts" of the equation live in a specific neighborhood.

4. The Big Picture: Why Does This Matter?

You might ask, "Why do we care about counting guards in a number city?"

Structure Reveals Secrets: By looking at how these polynomials behave (are they smooth hills? do their zeros form pretty patterns?), mathematicians can learn deep secrets about the numbers themselves.
The "Unimodal" Mystery: The paper shows that for simple number cities, the structure is very orderly (smooth hills). But as the city gets more complex (more prime factors), the order breaks down. This helps mathematicians understand the boundary between "simple" and "chaotic" in algebra.
Future Work: The author admits that for very complex cities (with three or more prime factors mixed together), the formulas get incredibly messy, and the patterns of the zeros are still a mystery. It's an open invitation for other detectives to solve the next layer of the puzzle.

Summary in a Nutshell

The author took a complex mathematical object (a graph made of numbers), built a "scorecard" (polynomial) to count specific social arrangements (guards and parties), and discovered that for many cases, these scorecards have beautiful, predictable shapes and their "ghosts" (zeros) live in specific, fascinating patterns. It's a mix of counting, geometry, and number theory, all wrapped up in a story about how numbers connect.

1. Problem Statement

The paper investigates the algebraic and combinatorial properties of comaximal graphs ( $\Gamma(R)$ ) associated with commutative rings, specifically focusing on the ring of integers modulo $n$ ( $\mathbb{Z}_n$ ).

The core problem involves determining and analyzing two specific graph polynomials for $\Gamma(\mathbb{Z}_n)$ :

The Independent Domination Polynomial ( $D_i(G, x)$ ): A generating function counting the number of independent dominating sets of a specific cardinality $k$ .
The Independence Polynomial ( $I(G, x)$ ): A generating function counting the number of independent sets of a specific cardinality $k$ .

The study aims to:

Derive explicit formulas for these polynomials for specific structural forms of $n$ (e.g., prime powers, products of two or three primes).
Analyze the unimodality (single-peaked coefficient sequence) and log-concavity (coefficients satisfying $a_k^2 \geq a_{k-1}a_{k+1}$ ) of these polynomials.
Investigate the location and nature of the zeros (roots) of these polynomials.

2. Methodology

The author employs a combination of graph theory, ring theory, and polynomial analysis:

Graph Decomposition: The paper utilizes the structural decomposition of $\Gamma(\mathbb{Z}_n)$ $Γ (Z_{n})$ . The vertex set is partitioned based on the greatest common divisor (GCD) of elements with $n$ $n$ . The graph is expressed as a join ( $\vee$ $\lor$ ) and union ( $\cup$ $\cup$ ) of cliques ( $K_m$ $K_{m}$ ) and null graphs (independent sets).
- Specifically, $\Gamma(\mathbb{Z}_n) \cong K_{\phi(n)} \vee (K_1 \cup G_2)$ , where $G_2$ is a subgraph determined by the proper divisors of $n$ .
Recursive Formulation: Theorems are derived to express the polynomials of $\Gamma(\mathbb{Z}_n)$ in terms of the polynomials of the subgraph $G_2$ . This allows for iterative calculation based on the prime factorization of $n$ .
Combinatorial Counting: The author explicitly counts independent dominating sets and independent sets by analyzing vertex partitions (e.g., sets of units, zero divisors, and specific GCD classes) and their adjacency rules.
Polynomial Analysis:
- Unimodality: Checked by analyzing the sequence of coefficients for a single peak.
- Log-concavity: Verified using the condition $a_k^2 \geq a_{k-1}a_{k+1}$ .
- Root Bounds: The Eneström-Kakeya theorem is applied to determine the annulus in the complex plane where the non-zero roots of the independence polynomial lie.

3. Key Contributions and Results

A. Independent Domination Polynomial ( $D_i$ )

The paper provides explicit formulas for $D_i(\Gamma(\mathbb{Z}_n), x)$ for various $n$ :

Prime $n=p$ : $D_i = px$ .
**Product of distinct primes $n=pq $:**$ D_i = (pq - p - q + 1)x + x^p + x^q$.
Product of three distinct primes $n=pqr$: A formula involving terms $x^{\phi(n)}$ , $x^{p+q+r-2}$ , $x^{pq}$ , $x^{pr}$ , and $x^{qr}$ .
Prime powers $n=p^m$ : $D_i = (p^m - p^{m-1})x + x^{p^{m-1}}$ .
General forms ( $n=p^{n_1}q^{n_2}$ and $n=p^{n_1}q^{n_2}r^{n_3}$ ): General recursive formulas are established.

Properties of $D_i$ :

Unimodality: $D_i(\Gamma(\mathbb{Z}_n), x)$ $D_{i} (Γ (Z_{n}), x)$ is unimodal if and only if:
- $n = p$ (any prime), or
- $n = p^m$ with $m=1$ or ( $m=p=2$ ), or
- $n = p^{n_1}q^{n_2}$ with $n_1=n_2=1, p=2, q=3$ .
Log-concavity: The polynomial is log-concave if and only if $p \neq 3$ and $m \neq 2$ (for prime powers). For $n=pq$, it fails log-concavity under specific conditions (e.g., $p=3$ or $p-q=2$ ).
Roots: For $n=pq$ (with $p, q > 2$ ), the only real root is $x=0$ . For $n=p^m$ ( $m \geq 3$ ), there is exactly one real root.

B. Independence Polynomial ( $I$ )

The paper derives formulas for $I(\Gamma(\mathbb{Z}_n), x)$ :

Prime $n=p$ : $I = 1 + px$.
**Product of distinct primes $n=pq $:**$ I = (\phi(n)-1)x + (1+x)^p + (1+x)^q - 1$.
Prime powers $n=p^m$ : $I = \phi(n)x + (1+x)^{p^{m-1}}$ .
General forms: Recursive formulas involving the independence polynomial of the subgraph $G_2$ .

Properties of $I$ :

Unimodality & Log-concavity:
- For $n=p$ , the polynomial is unimodal and log-concave.
- For $n=pq$, the polynomial is generally neither unimodal nor log-concave for large primes. It is unimodal/log-concave only for small cases like $p=2, q=3$ .
- For $n=p^m$ , the polynomial is unimodal (due to binomial coefficient patterns) but not log-concave (verified for $p=2$ ).
Roots:
- Using the Eneström-Kakeya theorem, the non-zero roots of $I(\Gamma(\mathbb{Z}_n), x)$ for $n=pq$ are bounded within the annulus $0 < |Z| < \frac{q-1}{2}$ .
- Numerical examples (e.g., $n=77$ ) show roots forming patterns near the boundary of a disc centered on the negative real axis.

4. Significance and Future Work

Theoretical Advancement: This work extends the study of graph polynomials from zero-divisor graphs to comaximal graphs, providing a bridge between ring-theoretic properties (factorization of $n$ ) and graph-theoretic invariants.
Structural Insight: The decomposition of $\Gamma(\mathbb{Z}_n)$ into joins of cliques and null graphs provides a powerful framework for calculating domination and independence parameters, which are generally NP-complete problems.
Open Problems:
- Determining explicit formulas for $D_i$ and $I$ for general $n$ (with more than 3 prime factors) remains difficult due to the complexity of the subgraph $G_2$ .
- Characterizing the exact curves of the limit of zeros for large $n$ .
- Investigating the relationship between the unimodality/log-concavity of these polynomials and the algebraic structure of the underlying ring $R$ for arbitrary commutative rings.

In conclusion, the paper successfully establishes a comprehensive framework for calculating and analyzing the independent domination and independence polynomials of comaximal graphs of $\mathbb{Z}_n$ , identifying precise conditions under which these polynomials exhibit desirable properties like unimodality and log-concavity.