The spread of generalized reciprocal distance matrix

Hechao Liu, Yufei HuangarXiv 2022 · DOI · arXiv

TL;DR

This paper explores the spectral properties of the generalized reciprocal distance matrix ($RD_\alpha$), a mathematical framework that unifies several distance-based graph matrices. The authors derive sharp upper and lower bounds for the "spread"—the difference between the largest and smallest eigenvalues—of this matrix across various graph structures, including bipartite graphs, graphs with specific clique numbers, and double star trees.

What Problem Does This Paper Address?

In spectral graph theory, researchers represent graphs as matrices to study their structural properties through the lens of linear algebra. Two common representations are the reciprocal distance matrix (or Harary matrix), which weights connections by the inverse of the distance between nodes, and the reciprocal distance signless Laplacian matrix.

Recently, a generalized version called $RD_\alpha$ was proposed to bridge these two concepts using a parameter $\alpha$ (where $0 \leq \alpha \leq 1$). While the largest eigenvalue (spectral radius) of such matrices is often studied, the spread—the range between the maximum and minimum eigenvalues—is equally important as it relates to a graph's expansion properties and structural regularity. Before this paper, sharp bounds for the $RD_\alpha$-spread were largely unknown. The authors aim to fill this gap by providing a comprehensive set of bounds and exact values for specific graph families.

Methods

The authors employ several classical and modern techniques from spectral linear algebra:

  • Frobenius Norms and Traces: By relating the sum of squared eigenvalues to the Frobenius norm of the $RD_\alpha$ matrix, the authors establish general bounds linked to the Harary index (the sum of all reciprocal distances in a graph).
  • Interlacing Theorems: They use Lemma 2.11 to show how the eigenvalues of a "quotient matrix" (a smaller matrix representing a partition of the graph) relate to the eigenvalues of the full graph. This is crucial for deriving bounds for bipartite graphs and graphs with a fixed clique number.
  • Matrix Decomposition: To solve the spectrum of double star graphs, the authors use a sophisticated block-matrix decomposition technique. This allows them to reduce a large, complex matrix into smaller, manageable blocks to find exact eigenvalue expressions.

Datasets

Not applicable. This is a theoretical mathematics paper; the results are proven analytically for all graphs within the specified classes rather than tested against empirical datasets.

Key Insights and Ideas

  • The Power of $\alpha$: The $RD_\alpha$ matrix is a convex combination of the transmission diagonal matrix and the Harary matrix. The paper shows that the behavior of the spread changes significantly depending on whether $\alpha$ is above or below $1/2$.
  • Regularity as a Benchmark: Many of the "sharp" bounds (where the inequality becomes an equality) are achieved by reciprocal transmission regular graphs—graphs where every vertex has the same total "closeness" to all other vertices.
  • Diameter Matters: For graphs with a diameter of 2, the spread can be bounded directly using the eigenvalues of the $A_\alpha$ matrix (a generalized adjacency matrix). However, for diameters $\geq 3$, the authors introduce a correction matrix ($M^*$) to account for the increased complexity of long-range reciprocal distances.
  • Double Star Symmetry: The authors demonstrate that double star trees ($S_{m,n}$) have a highly structured spectrum, where most eigenvalues are repeated, and the unique properties of the graph are captured by just four specific eigenvalues ($\theta_1$ through $\theta_4$).

Key Results

  • General Bounds: The paper provides a sharp upper bound for the spread of any connected graph based on the number of vertices ($n$), the Harary index ($H(G)$), and the parameter $\alpha$ (Theorem 2.2).
  • Clique Number Influence: Theorem 2.14 establishes a lower bound for the spread based on the clique number ($\omega$), showing that as the size of the largest complete subgraph increases, the minimum possible spread of the graph is constrained in a predictable way.
  • Bipartite Graphs: The authors determined specific lower bounds for bipartite graphs, which are often used to model systems with two distinct types of entities (e.g., users and products).
  • Exact Spectrum for Double Stars: The paper concludes with a complete characterization of the eigenvalues for double star trees, providing a closed-form solution for their $RD_\alpha$-spread.

Limitations and Future Work

The paper focuses strictly on the mathematical bounds and the spectrum of specific graph families. It does not explore:

  • Computational Complexity: While the bounds are analytical, the paper does not discuss the algorithmic efficiency of calculating these values for massive real-world networks.
  • Physical Applications: The Harary matrix is frequently used in chemical graph theory to predict molecular properties. Future work could investigate if the $RD_\alpha$-spread correlates with specific physical or chemical traits in molecules.
  • Other Graph Classes: The authors suggest that their methods could be extended to other classes, such as unicyclic graphs or "cacti" graphs, which were not covered here.

Summary updated

Abstract

The generalized reciprocal distance matrix $RD_α(G)$ was defined as $RD_α(G)=αRT(G)+(1-α)RD(G),\quad 0\leq α\leq 1.$ Let $λ_{1}(RD_α(G))\geq λ_{2}(RD_α(G))\geq \cdots \geq λ_{n}(RD_α(G))$ be the eigenvalues of $RD_α$ matrix of graphs $G$. Then the $RD_α$-spread of graph $G$ can be defined as $S_{RD_α}(G)=λ_{1}(RD_α(G))-λ_{n}(RD_α(G))$. In this paper, we first obtain some sharp lower and upper bounds for the $RD_α$-spread of graphs. Then we determine the lower bounds for the $RD_α$-spread of bipartite graphs and graphs with given clique number. At last, we give the $RD_α$-spread of double star graphs. Our results generalize the related results of the reciprocal distance matrix and reciprocal distance signless Laplacian matrix.
BibTeX
@misc{liu2022spread,
  author = {Hechao Liu and Yufei Huang},
  title = {{The spread of generalized reciprocal distance matrix}},
  year = {2022},
  eprint = {2207.05181},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2207.05181},
}
Figure