Degree-Based Weighted Adjacency Matrices: Spectra, Integrality, and Edge Deletion Effects

This paper investigates the spectral properties of degree-based weighted adjacency matrices for complete and crown multipartite graphs, characterizes families with three distinct eigenvalues and integral spectra, corrects previous findings on energy changes after edge deletion, and resolves an open problem regarding ISI energy in multipartite graphs.

The Gist

Imagine a city where every building is a vertex (a point) and every road connecting them is an edge. In mathematics, this is called a graph.

This paper is like a team of urban planners and physicists trying to understand the "vibrational energy" of these cities. But they aren't just looking at simple roads; they are looking at weighted roads.

The Core Concept: Weighted Roads

In a normal city map, a road is just a road. But in this paper, the "weight" of a road depends on how busy the buildings at either end are.

• If two small, quiet houses are connected, the road is light.
• If two massive skyscrapers are connected, the road is heavy.

The authors are studying a specific type of "traffic rule" called the Inverse Sum Indeg (ISI) weight. Think of it like a toll booth: the toll is calculated based on the size of the two buildings it connects. The bigger the buildings, the higher the toll.

The Main Goal: Measuring "City Energy"

The authors want to calculate the Energy of the city. In this context, "Energy" isn't electricity; it's a mathematical number that represents the total "vibration" or "activity" of the entire network.

• High Energy: The city is chaotic, highly connected, and active.
• Low Energy: The city is calm or broken up.

The big question they ask is: "What happens to the city's energy if we close one single road?"

The Plot Twist: Correcting the "Old Map"

Previously, other researchers (Bilal and Munir) published a map claiming that if you close a road in a Complete Graph (a city where every building is connected to every other building), the city's energy would increase. They thought closing a road made the city "more energetic."

The authors of this paper say: "Wait a minute, that's wrong."

Using their new, more precise calculations (specifically for the ISI weight), they prove the opposite:

• The Reality: When you close a road in a fully connected city, the energy decreases.
• The Analogy: Imagine a crowded dance floor where everyone is holding hands. If you cut one hand-hold, the whole group becomes slightly less "tense" and energetic. The system relaxes.

They found that the old researchers made a math error. For almost every type of weighted road they tested, closing a road makes the city calmer (lower energy).

The "Tripartite" Puzzle

The paper also tackles a specific type of city called a Tripartite Graph. Imagine a city divided into three distinct neighborhoods (Red, Blue, and Green). People can only travel between neighborhoods, never within their own.

• The old map claimed that if you closed a road between the Red and Blue neighborhoods, the energy would drop.
• The New Discovery: The authors found counter-examples. In many cases, closing that road actually increases the energy!
• The Metaphor: It's like a three-way traffic jam. Sometimes, removing a single lane forces traffic to reroute in a way that creates a new, more intense flow pattern, increasing the overall "stress" (energy) of the system.

The "Crown" City

The authors also studied Crown Graphs. Imagine a city built like a crown: two rings of buildings, where every building in the inner ring is connected to its partner in the outer ring, but the "spikes" of the crown are missing.

• They calculated the exact "vibration" (spectrum) of these cities.
• They figured out exactly when these cities have "whole number" energy (called Integral Spectra). It turns out, this only happens if the buildings have an even number of connections. It's like a puzzle where the pieces only fit perfectly if the numbers are even.

Summary of Findings

1. The Correction: In a fully connected city, closing a road lowers the energy. The old idea that it raises energy was a mistake.
2. The Surprise: In some three-part cities, closing a road can actually raise the energy, breaking the rule that "less connection = less energy."
3. The Crown: They solved the math puzzle for "Crown" cities, showing exactly when their energy levels are clean, whole numbers.

Why Does This Matter?

You might ask, "Who cares about the energy of a math city?"

• Chemistry: These graphs model molecules. The "energy" predicts how stable a molecule is. If you break a bond (close a road), does the molecule become more stable or less?
• Networks: It helps us understand how robust computer networks or social media connections are when a link fails.
• Math: It fixes errors in previous textbooks and gives us a better "rulebook" for how these complex systems behave.

In short, this paper is a mathematical fact-check that tells us: "Don't assume breaking a connection always makes things worse (or better). It depends entirely on the shape of the city and the rules of the road."

Technical Summary

Here is a detailed technical summary of the paper "Degree-Based Weighted Adjacency Matrices: Spectra, Integrality, and Edge Deletion Effects" by Bilal Ahmad Rather and Hilal Ahmad Ganie.

1. Problem Statement and Motivation

The paper addresses several open problems and inconsistencies in the spectral graph theory literature regarding degree-based weighted adjacency matrices (denoted as $\dot{A}(G)$ or $A_\phi(G)$). These matrices generalize the standard adjacency matrix by assigning edge weights based on a function $\phi(d_u, d_v)$ of the degrees of the incident vertices.

The specific problems tackled include:

• Spectral Characterization: Determining the spectra of complete multipartite graphs and crown multipartite graphs under various degree-based weight functions.
• Integrality: Identifying conditions under which these weighted matrices possess integer spectra (integral graphs).
• Edge Deletion Effects: Investigating how the energy (sum of absolute eigenvalues) and spectral radius of a graph change when a single edge is removed.
• Correction of Literature: The authors specifically aim to correct and refine results from a previous study by Bilal and Munir (2024) regarding the energy changes in complete graphs and regular tripartite graphs upon edge deletion, particularly for the Inverse Sum Indeg (ISI) matrix.

2. Methodology

The authors employ a combination of algebraic graph theory techniques:

• Equitable Partitions: They utilize the concept of equitable partitions to reduce large adjacency matrices of symmetric graphs (like complete multipartite graphs) into smaller quotient matrices. The eigenvalues of the quotient matrix, combined with specific structural properties (like independent sets or cliques), allow for the exact determination of the full spectrum.
• Matrix Decomposition: For graphs with edge deletions (e.g., $K_n - e$ or $K_{p,p,p} - e$), the authors decompose the vertex set into specific cells based on vertex degrees and neighborhood structures. They construct quotient matrices and, in complex cases (like the tripartite graph), utilize permutation matrices to split the space into invariant subspaces ($W_+$ and $W_-$) to solve for eigenvalues.
• Analytical and Numerical Verification: Theoretical derivations are supported by numerical computations using specific values of $n$ (order of the graph) and various weight functions $\phi$ (e.g., ISI, Arithmetic-Geometric, Sombor indices) to test conjectures and disprove previous theorems.

3. Key Contributions and Results

A. Spectra of Complete Multipartite Graphs ($K_{p_1, \dots, p_t}$)

• General Spectrum: The authors prove that the spectrum of $\dot{A}(K_{p_1, \dots, p_t})$ consists of the eigenvalue 0 with multiplicity $n-t$, and the remaining $t$ eigenvalues are the eigenvalues of a specific $t \times t$ quotient matrix $M$.
• Three Distinct Eigenvalues: They characterize when the matrix has exactly three distinct eigenvalues. It is proven that for $t \ge 3$ and $n > t$, the matrix has exactly three distinct eigenvalues if and only if the graph is regular (i.e., $p_1 = p_2 = \dots = p_t$).
• Integrality: Conditions for the spectrum to be integral are established. For a regular complete multipartite graph, the spectrum is integral if and only if $\phi(d, d)$ is an integer.
  • Specific Finding: For the ISI matrix ($\phi(x,y) = \frac{xy}{x+y}$), the spectrum is integral if and only if the degree $d$ is even.

B. Edge Deletion Effects on Complete Graphs ($K_n$)

• Correction of Previous Results: The paper refutes a claim in [Bilal and Munir, 2024] that the ISI energy of a complete graph increases upon edge deletion.
• New Theorem: The authors derive a precise condition for the spectral radius and energy to decrease upon edge deletion. The energy decreases if:
  $$\frac{\phi(d_n, d_n)}{\phi(d_1, d_n)} < \sqrt{\frac{n-2}{n-1}}$$
  where $d_n = n-1$ and $d_1 = n-2$.
• ISI Specifics: For the ISI index, the ratio $\frac{\phi(d_n, d_n)}{\phi(d_1, d_n)}$ is always greater than 1. Consequently, the ISI energy of a complete graph strictly decreases upon edge deletion.
• Conjecture: The authors conjecture that for "almost all" weight functions $\phi$, the energy of a complete graph decreases upon edge deletion.

C. Edge Deletion Effects on Regular Tripartite Graphs ($K_{p,p,p}$)

• Disproof of Theorem 6 & 7 [2]: The authors provide counterexamples showing that the ISI energy of a regular tripartite graph $K_{p,p,p}$ increases upon edge deletion for $p \ge 3$, contradicting previous literature which claimed it decreases.
• Spectral Calculation: They derive the exact ISI spectrum for $K_{p,p,p} - e$, which involves:
  • Eigenvalue 0 with multiplicity $3p-5$.
  • Two simple eigenvalues derived from a quadratic equation.
  • Three eigenvalues derived from the roots of a cubic polynomial.
• Numerical Evidence: Tables comparing $E(K_{p,p,p})$ and $E(K_{p,p,p}-e)$ for $p=3, 4, \dots$ confirm that $E(K_{p,p,p}-e) > E(K_{p,p,p})$.

D. Crown Multipartite Graphs

• The paper extends the spectral analysis to crown multipartite graphs ($C_{p, \dots, p}$), which are formed by removing a perfect matching from a complete multipartite graph.
• They provide the complete spectrum and energy formulas for these graphs.
• Integrality: Similar to the complete multipartite case, the spectrum is integral if and only if $\phi(d, d)$ is an integer.

E. Star Graphs

• The authors critique the analysis of star graphs in previous literature, noting that deleting an edge from a star graph results in a disconnected graph, making energy comparisons invalid.
• Instead, they analyze the effect of adding an edge to a star graph (creating a unicyclic graph) and show that the ISI energy increases.

4. Significance

• Theoretical Correction: The paper is significant for correcting erroneous results in recent literature regarding the monotonicity of graph energy under edge deletion. It establishes that the behavior of energy is highly dependent on the specific weight function $\phi$ and the graph structure.
• Unified Framework: It provides a unified spectral framework for a wide class of degree-based topological indices (ISI, AG, GA, Zagreb, Sombor, etc.) applied to complete and crown graphs.
• Integrality Conditions: The clear conditions provided for when these complex weighted matrices yield integer spectra contribute to the classification of integral graphs in the context of chemical graph theory.
• Methodological Rigor: The use of equitable partitions and subspace decomposition offers a robust method for analyzing the spectra of graphs with edge modifications, which can be applied to other graph families.

In summary, this paper advances the understanding of degree-based spectral graph theory by providing exact spectral formulas for complex graph families, establishing rigorous conditions for integrality, and correcting fundamental misconceptions regarding how graph energy behaves when edges are removed.