Maximizing the Spectral Radius of Constrained Graphs

81 concepts28 papers5 proposals

In classical extremal graph theory, the central question is quantitative: how many edges can a graph possess before it is forced to contain a specific forbidden subgraph? This is the domain of Turán-type problems. However, simply counting edges fails to capture the intricate connectivity, centrality, and internal topology of a network.

Spectral extremal graph theory addresses this limitation by shifting the focus from edge counts to the spectral radius ($\lambda_1$)—the largest eigenvalue of the graph's adjacency matrix (or related matrices like the Laplacian). The spectral radius acts as a sensitive proxy for structural density and walk connectivity. As noted by Sun et al. in Subdivision-free graphs with the maximum spectral radius, the spectral radius captures global path properties that raw edge counts cannot. The core objective of this research direction is to identify the exact graph structures that maximize this spectral measure under various structural constraints, such as forbidden minors, fixed independence numbers, or bounded connectivity.

The Geometry of Extremality: Core-Periphery and Star-like Topologies

Why do certain graphs maximize the spectral radius while avoiding forbidden structures? Intuitively, to maximize the largest eigenvalue, a graph must concentrate its edges into a dense core rather than spreading them out uniformly. While a regular graph distributes its connectivity evenly, an extremal graph under structural constraints typically polarizes into a highly asymmetric core-periphery architecture.

Consider what happens when we try to maximize the spectral radius of a block graph while keeping its dissociation number fixed. Das et al. demonstrate in Maximization of the spectral radius of block graphs with a given dissociation number that the optimal configuration is a centralized clique topology—a star-like arrangement where all maximal cliques share a single common cut vertex. By concentrating connectivity around a single central hub, the graph maximizes the density of short closed walks, which directly drives up the largest eigenvalue.

Distributed Topology (Lower Spectral Radius)      Centralized Topology (Maximum Spectral Radius)
       O---O                                                   O     O
      /     \                                                   \   /
     O       O                                                 --[Hub]--
      \     /                                                   /   \
       O---O                                                   O     O

A similar structural convergence occurs when avoiding topological subgraphs. Sun et al. show in Subdivision-free graphs with the maximum spectral radius that graphs maximizing the spectral radius without creating a forbidden subdivision converge to a "generalized book" structure: a small, dense core clique connected to every vertex of a large independent set. In this configuration, the peripheral vertices form a saturated subgraph; adding any further edge between them would inevitably trigger the forbidden subdivision. This core-periphery split allows the graph to pack its core to the absolute maximum limit while safely isolating the periphery.

This centralized pattern also holds in higher-order structures like hypergraphs. Liu et al. show in On the α-spectral radius of the k-uniform supertrees that unique hyperstar-like configurations are spectrally optimal when maximizing the spectral radius under independence constraints.

The Mechanics of Extremal Proofs: Surgery and Shifting

To prove that a specific graph structure is truly extremal, researchers rely on a dynamic toolkit known as localized graph surgery or spectral edge-shifting. The intuition behind these techniques relies on the Perron vector—the unique positive eigenvector corresponding to the spectral radius.

By the Rayleigh quotient, the spectral radius can be viewed as a weighted sum of the products of vertex weights (from the Perron vector) across all edges:

$$\lambda_1 = \frac{x^T A x}{x^T x} = \frac{2 \sum_{uv \in E} x_u x_v}{\sum_{v \in V} x_v^2}$$

If an edge connects two vertices with high Perron weights, it contributes significantly more to the spectral radius than an edge connecting low-weight vertices. Therefore, if a graph is not yet optimal, one can perform "surgery" by deleting an edge from a structurally weak part of the graph and adding an edge between vertices with higher Perron weights.

Combinatorial Invariants as Structural Constraints

The exact shape of the extremal graph is dictated by the specific combinatorial invariants held constant during optimization. Invariants like the independence number ($\alpha$), matching number, or connectivity act as rigid boundaries that shape the permissible core and periphery.

For instance, Das et al. prove in On the spectral radius of bi-block graphs with given independence number α that the maximum spectral radius is uniquely achieved by the complete bipartite graph $K_{\alpha, k-\alpha}$. Here, the independence number acts as a rigid constraint that forces a highly regular bipartite partition to maximize the spectrum.

When multiple constraints interact, the problem becomes significantly more complex. Liu et al. analyze this in The maximum Aα-spectral radius of t-connected graphs with bounded matching number, showing how combinations of complete graphs and their unions emerge as the unique maximizers under simultaneous connectivity and matching bounds. Similarly, Chen et al. in The spectral radius of minor-free graphs adapt these principles to graphs excluding specific minors, demonstrating that spectral extremal graphs mirror classical edge-extremal graphs but exhibit distinct spectral signatures due to their path-like constraints.

Generalizing to Laplacian and Alternative Graph Matrices

The pursuit of spectral extremality extends beyond the standard adjacency matrix to the Laplacian matrix ($\mathcal{L} = D - A$), where eigenvalues provide deep insights into graph cuts and connectivity.

For non-regular graphs, Bo Liu shows in A note on the largest eigenvalue of non-regular graphs that graphs maximizing the largest eigenvalue among non-regular structures exhibit minimal deficiency—meaning almost all vertices maintain the maximum degree $\Delta$, leaving only one or two vertices to deviate. Wang et al. in Improved Upper Bounds for the Laplacian Spectral Radius of a Graph similarly show that the maximum possible value of the Laplacian spectral radius is reached in highly symmetric regular or semiregular bipartite graphs.

To find lower bounds on the Laplacian, researchers often look at the inertia (the number of positive, negative, and zero eigenvalues) of the adjacency matrix. Charles et al. demonstrate in Nonpositive Eigenvalues of Hollow, Symmetric, Nonnegative Matrices and Nonpositive eigenvalues of the adjacency matrix and lower bounds for Laplacian eigenvalues that the number of nonpositive eigenvalues in a graph's adjacency matrix directly constrains and provides sharp lower bounds for its Laplacian eigenvalues.

Finally, Nathan Reff extends these principles to higher-order and oriented structures in Lower bounds for the Laplacian spectral radius of an oriented hypergraph, introducing parameterized template graphs and interlacing theorems to bound complex hypergraph spectra. This demonstrates that the core mechanisms of spectral extremality—centralization, edge-shifting, and structural constraints—remain robust across diverse mathematical representations of networks.

Key Foundational Work

A note on the largest eigenvalue of non-regular graphs (2008) — contributed 3 concept elements to this direction.
Improved Upper Bounds for the Laplacian Spectral Radius of a Graph (2011) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 25 papers
  2. Version 1 · 2026-10-04 · 51 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_spectral_radius_maximization_f0b56d1f,
  title = {spectral radius maximization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/spectral-radius-maximization/rdr_f0b56d1f19bb414bbfa0285fd47bc77b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_spectral_radius_maximization_f0b56d1f_v2,
  title = {spectral radius maximization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/spectral-radius-maximization/rdr_f0b56d1f19bb414bbfa0285fd47bc77b/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake