On the spectral radius of clique trees with a given zero forcing number

Joyentanuj DasarXiv 2023 · DOI · arXiv

Abstract

Let $G(n,k)$ be the class of clique trees on $n$ vertices and zero forcing number $k$, where $\lfloor \frac{n}{2} \rfloor + 1 \le k \le n-1$ and each block is a clique of size at least $3$. In this article, we proved the existence and uniqueness of a clique tree in $G(n,k)$ that attains maximal spectral radius among all graphs in $G(n,k)$. We also provide an upper bound for the spectral radius of the extremal graph.

Introduction

In spectral graph theory, the spectral radius—defined as the largest eigenvalue of a graph's adjacency matrix—serves as a critical indicator of structural properties such as connectivity, synchronizability, and information spread. A recurring theme in this field is the identification of "extremal graphs": specific structures that maximize or minimize a given spectral parameter under certain constraints.

This paper investigates the maximal spectral radius within the class of clique trees $G(n, k)$. A clique tree is a connected graph where every block is a clique (a complete subgraph). While standard trees are composed of cliques of size 2 (edges), the graphs studied here consist of cliques of size at least 3 joined at cut-vertices.

A general clique tree structure where blocks are cliques joined at cut-vertices.

The Zero Forcing Constraint

The primary constraint in this study is the zero forcing number ($k$). Originating from the study of minimum rank problems in linear algebra, zero forcing is defined by a color-change rule: if a colored vertex has exactly one uncolored neighbor, it "forces" that neighbor to take its color. The zero forcing number $k$ is the minimum size of an initial set of colored vertices required to color the entire graph.

For the class of clique trees where each block has size at least 3, the zero forcing number is elegantly related to the number of blocks $b$ by the formula $k = n - b$. This relationship is pivotal, as it bounds the structural complexity of the graph for a fixed $n$ and $k$, preventing the graph from simply collapsing into a single giant clique.

Methodology: Shifting and Simplification

The author identifies the extremal graph through a series of graph transformations and matrix analyses:

  1. Block Shifting: The core proof demonstrates that "shifting" blocks from various cut-vertices to a single, central cut-vertex increases the spectral radius while preserving the zero forcing number. This process naturally leads toward a star-like configuration.
  2. Equitable Quotient Matrices: To calculate the spectral radius of complex clique trees, the author employs equitable partitions. This technique simplifies the large $n \times n$ adjacency matrix into a much smaller $3 \times 3$ quotient matrix. Because the quotient matrix shares the same largest eigenvalue as the original matrix, the problem becomes computationally tractable.
  3. Perron-Frobenius Theory: The properties of the principal eigenvector (the Perron vector) are used to justify why specific vertex movements necessarily increase the spectral radius.

The Extremal Graph: The "Clique Star"

The central finding of the paper is that the maximal spectral radius is attained by a unique "star-like" clique tree, denoted as $\mathcal{G}(n, k) = K_{2k-n+2} \odot K_3^{(n-k-1)}$. This graph consists of one large clique ($K_{2k-n+2}$) and several smaller 3-vertex cliques ($K_3$) all sharing a single common vertex.

The extremal graph structure maximizing the spectral radius for a given zero forcing number.

Key Results and Spectral Bounds

Beyond identifying the extremal graph, the paper provides analytical tools to characterize its spectrum:

  • Characteristic Polynomial: The spectral radius of $\mathcal{G}(n, k)$ is the largest root of the cubic polynomial: $f(x) = x^3 + (n-2k-1)x^2 - (2n-2k-1)x + k - (n-k-1)(2n-2k+1)$.

  • Upper Bounds: The author establishes concrete upper bounds for the spectral radius $\rho(G)$ in terms of $n$ and $k$. These bounds allow researchers to estimate the spectral properties of such networks without performing a full eigendecomposition.

Conclusion

By bridging combinatorial graph theory and matrix analysis, this work provides a complete characterization of the clique trees that maximize spectral radius for a given zero forcing number. While the study focuses on blocks of size $\ge 3$, it provides a foundation for future research into minimizing the spectral radius or extending these findings to broader graph classes.

Summary updated

Abstract

Let $G(n,k)$ be the class of clique trees on $n$ vertices and zero forcing number $k$, where $\left \lfloor \frac{n}{2} \right \rfloor + 1 \le k \le n-1$ and each block is a clique of size at least $3$. In this article, we proved the existence and uniqueness of a clique tree in $G(n,k)$ that attains maximal spectral radius among all graphs in $G(n,k)$. We also provide an upper bound for the spectral radius of the extremal graph.
BibTeX
@misc{das2023spectral,
  author = {Joyentanuj Das},
  title = {{On the spectral radius of clique trees with a given zero forcing number}},
  year = {2023},
  eprint = {2308.02975},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2308.02975},
}
Figure