Minimal spectral radius of graphs with given matching number

Jiaqi Liu, Zhenzhen Lou, Vilmar Trevisan · 2026

Read Minimal spectral radius of graphs with given matching number by Jiaqi Liu, Zhenzhen Lou, Vilmar Trevisan (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-18223.txt.

Introduction

Jiaqi Liu, Zhenzhen Lou, and Vilmar Trevisan find the graphs with the smallest spectral radius for a fixed matching size. Their 2026 preprint takes up the Brualdi-Solheid problem. That problem asks which graph in a class hits the extreme spectral radius, largest or smallest. The class here is all graphs with a given order and matching number. A matching is a set of edges that share no vertices, and its size limits how a graph can spread.

The authors aim to identify the spectrally minimal graphs in that family. Extremal results show which shapes sit at the edge of what is possible. Spectral radius links to walks, spread, and network behavior. The work adds a solved case to a classic problem.

Catalog record

CREATORJiaqi Liu, Zhenzhen Lou, Vilmar Trevisan
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE54 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-18223

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Minimal spectral radius of graphs with given matching number Jiaqi Liu, Zhenzhen Lou, Vilmar Trevisan Abstract . The Brualdi-Solheid problem asks which graph achieves the extremal (maximum or minimum) spectral radius for a given class of graphs. This paper addresses the Brualdi-Solheid problem for 𝒢 n , β \mathcal{G}_{n,\beta} , the family of graphs with order n n and matching number β \beta , aiming to identify its spectrally minimal graphs i.e., those that minimize the spectral radius ρ ⁡ ( G ) \rho(G) . We introduce the novel concept of “quasi-adjacency” relation, developing a unified structural classification framework for trees in 𝒢 n , β \mathcal{G}_{n,\beta} , which clarifies structural properties and provides a constructive method to generate trees with fixed β \beta . By showing that all spectrally minimal graphs in 𝒢 n , β \mathcal{G}_{n,\beta} are trees, we further narrow the search for extremal graphs. Additionally, we apply this framework to the representative cases β = 2 , 3 , 4 \beta=2,3,4 , obtaining the minimizers by explicit structural formulas involving parameters related to n n . Keywords: spectral radius; matching number; tree; extremal problem AMS subject classifications: 05C50; 05C35 1. Introduction Since its formulation by Brualdi and Solheid in 1986 [ 1 ] , the following problem has emerged as a cornerstone of spectral graph theory. Problem 1 . ( [ 1 ] ) For a given family of graphs \mathbb{G} , determine \min\left\{\rho(G):G\in\mathbb{G}\right\} , and \max\left\{\rho(G):G\in\mathbb{G}\right\} , and characterize the graphs that attain these extreme values. Over the past decades, researchers have extensively explored the relationships between the spectral radius and other graph invariants, leading to significant advancements that can be found in the vast available literature. For the independence number \alpha , Ji and Lu [ 16 ] determined the graphs with the maximal spectral radius among all trees on n vertices with independence number \alpha , where \lceil\tfrac{n}{2}\rceil\leq\alpha\leq n-1 . Du and Shi (2013) [ 6 ] showed that blowing up each vertex of a path of order \alpha into a clique of order k minimizes the spectral radius among connected graphs of order k\alpha when \alpha=3,4 , and conjectured this holds for all \alpha\in\mathbb{N} . Xu et al. (2009) [ 32 ] characterized the minimizers for \alpha\in\{1,2,\lfloor\frac{n}{2}\rfloor,\lfloor\frac{n}{2}\rfloor+1,n-3,n-2,n-1\} , while Lou and Guo (2022) [ 24 ] proved that minimizers for \alpha\geq\lfloor\frac{n}{2}\rfloor must be trees and characterized those for \alpha=n-4 , for n\geq 19 . For the diameter d , Guo and Zhou [ 10 ] determined the unique tree with the maximum spectral radius among all trees of a given diameter. Kumar et al. (2025) [ 17 ] and Wang et al. (2023) [ 33 ] characterized extremal trees and unicyclic/bicyclic graphs, respectively, while He and Lu (2022) [ 11 ] determined the maximum spectral radius of trees with fixed odd diameter. Further related results can be found in [ 4 , 10 , 13 , 16 , 20 , 29 ] . Regarding the domination number \gamma , Liu et al. [ 23 ] and Hu et al. [ 15 ] identified minimizers for specific values of \gamma , while Xing and Zhou [ 31 ] investigated graphs with maximal Laplacian and signless Laplacian spectral radii. Regarding the girth, Lou et al. [ 25 ] determined the graphs maximizing the spectral radius among those with odd girth k and odd number of edges m . Patra and Sahoo [ 27 ] studied the minimization of the Laplacian spectral radius of unicyclic graphs with fixed girth. Further related results can be found in [ 4 , 13 ] . Despite these advancements, a critical gap remains: the Brualdi-Hoffman problem has not been systematically addressed for graphs with a fixed matching number \beta . Early work by Hou and Li (2002) [ 14 ] provided upper bounds on the spectral radius of trees with fixed n and \beta , and Feng et al. (2007) [ 9 ] characterized maximizers for \beta -constrained graphs. Li and Chang (2014) [ 19 ] and Sun et al. (2017) [ 30 ] studied minimal Laplacian and spectral radii of trees for specific n=k\beta+1 , and Zhai et al. (2022) [ 35 ] determined maximal Q -spectral radii for graphs with fixed size and \beta (see also [ 3 , 5 , 22 ] ). However, the structural characterization of spectrally minimal graphs for general n and \beta —a fundamental aspect of the Brualdi-Hoffman problem—remains unresolved. To fill this gap, we focus on the following core problem: Problem 2 . For the family \mathcal{G}_{n,\beta} of graphs with order n and matching number \beta , what are the spectrally minimal graphs (i.e., those minimizing \rho(G) )? We recall that for a graph G=(V,E) , a matching M\subseteq E is a set of edges where no two distinct edges are adjacent; a maximum matching is one with the largest possible cardinality, called the matching number and denoted by \beta of G . A perfect matching is a maximum matching that covers every vertex in G . Additional key concepts include quasi-pendant vertices (the unique neighbors of pendant vertices), blocks (maximal connected subgraphs without cut vertices), and the spectral radius \rho(G) (the largest eigenvalue of the adjacency matrix A(G) of G ). In this work, we study Problem 2 . The main contributions are as follows. First, we establish a critical structural result: using a spectral radius comparison model, proof by contradiction, and graph structure simplification techniques, we prove that all spectrally minimal graphs in \mathcal{G}_{n,\beta} must be trees. This result drastically narrows the search space for minimizers from general graphs to trees, a theoretical breakthrough that simplifies subsequent analysis. Second, we introduce the new concept of “quasi-adjacency” relation to develop a unified structural classification framework for trees in \mathcal{G}_{n,\beta} . This framework clarifies the structural properties of such trees and provides a constructive method to generate trees with a fixed \beta , resolving the lack of systematic structural understanding in prior work. Third, we apply this framework to the specific cases \beta=2,3,4 (representative values that generalize to larger \beta ) and classify trees in \mathcal{G}_{n,\beta} into distinct subclasses. Through comprehensive spectral radius analysis—including constructing characteristic equations of adjacency matrices to rule out subclasses, and deriving strict spectral radius inequalities to exclude others—we characterize the spectrally minimal graphs. For completeness, we recall that if G\in\mathcal{G}_{n,\beta} and \beta=1 , then G is either a triangle ( n=3 ) or the star K_{1,n-1} . It is clear that K_{1,n-1} achieves the minimal spectral radius. For \beta=2 , we derive the minimizer among all graphs in \mathcal{G}_{n,2} as follows. a b a b c Figure 1. The graphs T_{2}(a,b) (left) and T_{3}(a,b,c) (right) . Theorem 1.1 . Let T_{2}^{*} be the graph with the minimal spectral radius among all graphs in \mathcal{G}_{n,2} , with n\geq 4 . Then T_{2}^{*}\cong T_{2}\left(\left\lfloor\tfrac{n-3}{2}\right\rfloor,\left\lceil\tfrac{n-3}{2}\right\rceil\right) (see Fig. 1 , left). For \beta=3 , we derive the minimizer among all graphs in \mathcal{G}_{n,3} as follows. Theorem 1.2 . Let T_{3}^{*} be an extremal graph with the minimum spectral radius over all graphs in T_{3}(a,b,c) (see Fig. 1 , right), where a+b+c=n-5 ( n\geq 11 ). Then T_{3}^{*}\cong\begin{cases}T_{3}\!\left(s+1,\,s-2,\,s+1\right),&\text{if }n-5=3s,\\ T_{3}\!\left(s+1,\,s-1,\,s+1\right),&\text{if }n-5=3s+1,\\ T_{3}\!\left(s+1,\,s,\,s+1\right),&\text{if }n-5=3s+2.\end{cases} For \beta=4 , we derive the minimizer among

Read the complete text