Domination polynomial of co-maximal graphs of integer modulo ring

This paper investigates the domination polynomial of the co-maximal graph $\Gamma(\mathbb{Z}_n)$ by deriving explicit formulas for specific cases of $n$, establishing structural connections for general $n$, and analyzing the unimodality, log-concavity, and modulus bounds of its roots.

The Gist

Imagine you are the mayor of a bustling, futuristic city called Modulo City (represented mathematically as $\mathbb{Z}_n$). This city has $n$ citizens, numbered from 0 to $n-1$.

In this city, people can form friendships based on a very specific rule: Two citizens are friends if, when you combine their "powers" (mathematically, their ideals), they can generate the entire city. In simpler terms, if you take citizen $A$ and citizen $B$, and mix their unique traits, you can create any other citizen in the city. If they can do this, they are connected by a friendship line (an edge). If not, they are strangers.

This map of friendships is called the Co-maximal Graph.

Now, the mayor has a problem: Security. The city needs to place "Watchmen" (dominating sets) at various locations. A Watchman is a citizen who can see themselves and everyone they are directly friends with. The goal is to find the smallest number of Watchmen needed to cover the whole city, or to count every possible way you could arrange Watchmen to cover the city, regardless of how many you use.

This paper, written by Bilal Ahmad Rather, is essentially a mathematical blueprint for solving this security puzzle for Modulo City. Here is the breakdown in plain English:

1. The Magic Formula (The Domination Polynomial)

The author creates a special "recipe book" called a Domination Polynomial. Think of this polynomial as a giant calculator that tells you:

• "If you use 1 Watchman, here is how many ways you can do it."
• "If you use 2 Watchmen, here is how many ways."
• "If you use 3 Watchmen, here is how many ways."

The paper derives exact formulas for this recipe book for specific types of cities (when the number of citizens $n$ is a prime number, a power of a prime, or a product of two primes).

2. The City's Structure (The Blueprint)

The author realizes that Modulo City isn't just a random mess of connections. It has a hidden structure, like a layered cake or a set of nested Russian dolls.

• The "Super-Connected" Layer: There is a group of citizens (those relatively prime to $n$) who are friends with everyone else. They are the VIPs.
• The "Isolated" Layer: There are groups of citizens who are only friends with the VIPs but not with each other.
• The "Zero" Citizen: The number 0 is a special case; it's friends with almost no one (except the VIPs).

By understanding this structure, the author can break the complex city down into smaller, manageable neighborhoods. He uses a mathematical tool called the "Join" (which is like gluing two groups together so everyone in Group A becomes friends with everyone in Group B) to rebuild the city's friendship map and calculate the security arrangements.

3. The "Hill" Shape (Unimodality and Log-Concavity)

One of the most fascinating discoveries in the paper is about the shape of the security arrangements.

Imagine you are stacking blocks to build a hill.

• You start with very few Watchmen (hard to cover the city, so few arrangements).
• As you add more Watchmen, the number of ways to arrange them grows rapidly.
• You reach a peak (the "mode") where there are the most possible ways to arrange your team.
• After the peak, as you add even more Watchmen, the number of arrangements starts to shrink again (because you have so many people that it's hard to find new unique combinations).

The paper proves that for these cities, the number of arrangements always follows this smooth single-peak hill shape (called Unimodal). It doesn't go up, down, up, and down again. It's a nice, smooth hill.

Furthermore, the paper proves the hill is Log-Concave. In plain English, this means the hill is "thick" and "stable." The number of arrangements doesn't fluctuate wildly; it grows and shrinks in a very predictable, smooth mathematical curve. This is important because it suggests the city's security structure is robust and orderly, not chaotic.

4. The "Ghost" Watchmen (Roots of the Polynomial)

Finally, the author looks at the "roots" of the polynomial. In math, roots are the numbers that make the equation equal zero.

• Think of these roots as "Ghost Watchmen." They are imaginary numbers (complex numbers) that don't exist in the real world but hold the secret to the polynomial's behavior.
• The author uses a famous theorem (Eneström–Kakeya) to draw a "fence" around where these ghosts live. He proves that all these ghosts stay within a specific distance from the center of the city. This helps mathematicians predict how the polynomial behaves without having to calculate every single number.

Summary

In short, this paper takes a complex mathematical object (a graph based on number theory) and:

1. Maps it out: It shows how the "citizens" (numbers) are connected.
2. Counts the possibilities: It gives a formula to count every way to secure the city.
3. Proves it's orderly: It shows that the number of ways to secure the city follows a beautiful, smooth, single-peak curve (like a bell curve or a hill).
4. Locates the secrets: It finds the boundaries for the "ghost" numbers that define the polynomial's shape.

It's a story about finding order, symmetry, and predictability in the seemingly chaotic world of numbers and connections.

Technical Summary

Here is a detailed technical summary of the paper "Domination polynomial of co-maximal graphs of integer modulo ring" by Bilal Ahmad Rather.

1. Problem Statement

The paper investigates the domination polynomial, denoted as $D(G, x)$, for the co-maximal graph $\Gamma(\mathbb{Z}_n)$ associated with the ring of integers modulo $n$.

• Context: In graph theory, a dominating set $S$ is a subset of vertices such that every vertex not in $S$ is adjacent to at least one vertex in $S$. The domination polynomial counts the number of dominating sets of each possible cardinality $k$.
• Challenge: Calculating the domination polynomial is generally NP-hard because determining the domination number $\gamma(G)$ is NP-complete.
• Specific Object: The co-maximal graph $\Gamma(\mathbb{Z}_n)$ has the ring elements $\mathbb{Z}_n$ as vertices. Two distinct elements $a$ and $b$ are adjacent if and only if the ideal generated by them is the whole ring ($a\mathbb{Z}_n + b\mathbb{Z}_n = \mathbb{Z}_n$), which is equivalent to $\gcd(a, b) = 1$ in the context of $\mathbb{Z}_n$.
• Goal: The author aims to derive explicit formulas for $D(\Gamma(\mathbb{Z}_n), x)$ for specific forms of $n$, analyze the structural properties of these polynomials (unimodality and log-concavity), and establish bounds for the moduli of their roots (domination zeros).

2. Methodology

The author employs a combination of algebraic graph theory and combinatorial analysis:

• Structural Decomposition: The paper utilizes the canonical decomposition of $n = p_1^{n_1} p_2^{n_2} \dots p_r^{n_r}$. The vertex set of $\Gamma(\mathbb{Z}_n)$ is partitioned based on the greatest common divisor of elements with $n$.
  • Let $A_d = \{x \in \mathbb{Z}_n : \gcd(x, n) = d\}$.
  • The graph is decomposed into induced subgraphs corresponding to these sets $A_d$, the set of units $U(\mathbb{Z}_n)$, and the zero element $\{0\}$.
• Graph Operations: The structure of $\Gamma(\mathbb{Z}_n)$ is identified as a join ($\vee$) of a complete graph (formed by units) and a union of other subgraphs. Specifically, $\Gamma(\mathbb{Z}_n) \cong K_{\phi(n)} \vee (\{0\} \cup G_2)$, where $G_2$ is a complex subgraph formed by non-unit, non-zero elements.
• Recursive Formulas: The author applies known properties of domination polynomials for graph unions and joins:
  • $D(G_1 \cup G_2, x) = D(G_1, x) \cdot D(G_2, x)$
  • $D(G_1 \vee G_2, x) = ((1+x)^{n_1}-1)((1+x)^{n_2}-1) + D(G_1, x) + D(G_2, x)$
• Combinatorial Analysis: For specific $n$, the author counts dominating sets by analyzing the connectivity of the subgraph $G_2$ (e.g., identifying it as complete bipartite, tripartite, or null graphs).
• Analytical Tools:
  • Unimodality/Log-concavity: Checked via coefficient sequences and Newton's inequalities.
  • Root Bounds: The Eneström–Kakeya theorem is used to bound the moduli of the complex roots of the polynomial.

3. Key Contributions and Results

A. Explicit Formulas for Specific $n$

The paper derives exact expressions for the domination polynomial in several cases:

1. Prime $n = p$:
   • $\Gamma(\mathbb{Z}_p) \cong K_p$.
   • $D(\Gamma(\mathbb{Z}_p), x) = \sum_{i=1}^p \binom{p}{i} x^i = (1+x)^p - 1$.
2. Prime Power $n = p^m$ ($m \ge 2$):
   • The graph structure involves a join of a clique of units and a null graph of isolated vertices plus a specific subgraph.
   • Formula: $D(\Gamma(\mathbb{Z}_{p^m}), x) = (1+x)^{p^{m-1}} \sum_{i=1}^p \binom{p}{i} x^i + x^{p^{m-1}}$.
3. Product of Two Primes $n = pq$ ($p < q$):
   • The subgraph $G_2$ is identified as a complete bipartite graph $K_{p-1, q-1}$.
   • The polynomial is expressed as a combination of binomial expansions and cross terms involving $p$ and $q$.
4. General Form $n = p^{n_1}q^{n_2}$:
   • A complex structural expression is derived involving sums of binomial coefficients based on the Euler totient function and the specific divisors of $n$.
5. Product of Three Primes $n = pqr$:
   • The paper provides a block diagram (Figure 1) and a summation formula for the subgraph $G_2$, which is a tripartite graph with specific connections.

B. Structural Properties

• Unimodality and Log-concavity:
  • The paper proves that for $n = p^m$ and $n = pq$, the domination polynomials are unimodal (coefficients increase to a peak and then decrease) and log-concave (satisfy $a_k^2 \ge a_{k-1}a_{k+1}$).
  • This is significant because it implies a smooth distribution of dominating sets of various sizes, which is a desirable property in network reliability analysis.
• Inequalities:
  • Theorem 2.7 establishes lower bounds for $D(\Gamma(\mathbb{Z}_n), x)$ based on the number of distinct prime factors of $n$, with equality holding only when $n$ is a prime power.

C. Analysis of Roots (Zeros)

• Bounds on Moduli: Using the Eneström–Kakeya theorem, the author establishes that the non-zero complex roots $Z$ of $D(\Gamma(\mathbb{Z}_n), x)$ lie within specific annular regions in the complex plane.
  • For $n=p^m$, roots lie in $0 < |Z| < R$, where$R$is a function of$p$and$m$.
  • For $n=pq$, roots lie in $0 < |Z| < \frac{pq-1}{2}$.
• Visualization: The paper includes graphical representations of the roots for specific cases (e.g., $n=25$ and $n=15$), showing their distribution in the complex plane.

4. Significance

• Theoretical Advancement: The paper extends the understanding of domination polynomials from general graphs to a specific, algebraically defined class of graphs (co-maximal graphs of rings). It bridges algebraic number theory (properties of $\mathbb{Z}_n$) with algebraic graph theory.
• Computational Insight: By providing explicit formulas for non-trivial cases (like $p^m$ and $pq$), the paper offers a way to compute these polynomials without brute-force enumeration, which is crucial for larger $n$.
• Combinatorial Characterization: The demonstration of unimodality and log-concavity adds to the growing body of literature suggesting that many graph polynomials arising from algebraic structures possess these "nice" combinatorial properties.
• Applications: Understanding the domination polynomial helps in network design, specifically for broadcasting, facility location, and monitoring, where the number of dominating sets of a certain size indicates the robustness and redundancy of the network.

5. Conclusion and Future Work

The author concludes that while explicit formulas are derived for $n$ being a prime, a prime power, or a product of two primes, the general case for arbitrary $n$ remains complex due to the intricate structure of the subgraph $G_2$.
Future directions suggested include:

• Deriving explicit formulas for $n$ with three or more distinct prime factors.
• Further investigation into the distribution of domination zeros for general $n$.
• Proving the unimodality and log-concavity for the general case of $\Gamma(\mathbb{Z}_n)$.