Graph theorists often ask which graph, among all graphs obeying some structural rule, has the largest spectral radius: the largest eigenvalue of the adjacency matrix, which measures how fast walks multiply in the graph. For tree-like graph families the answers are nearly always "star-like", with every piece glued to one central vertex. The proofs, however, are bespoke. Each paper moves edges toward high-weight vertices until the conjectured winner appears, and this only works when the moves provably keep the structural rule intact. Combinatorialists studying domination and identification codes solve a mirror-image problem with a different tool. They prove bounds by induction over the block-cut tree, the tree that records how the 2-connected pieces of a graph ("blocks") hang off one another, and they strengthen the induction hypothesis with a small "boundary state" at each cut vertex. The two communities target the same graph classes and almost never share methods.
We propose to carry an exact spectral quantity through that induction. To each rooted branch of the block-cut tree we attach a single function of a real variable. When branches are glued at a vertex, these functions add, and they pass upward through each block by a closed-form, monotone rule. The induction hypothesis then compares functions pointwise instead of comparing numbers, which is the induction community's "hypothesis strengthening" applied to eigenvalues. Spectral extremal problems on block graphs, under any constraint that the block-cut tree can compute with finitely many boundary states, become a dynamic program whose states are rational functions. A finite set of pointwise dominance checks, verified exactly, can then be turned into an extremal theorem valid for every order $n$. The first target is an explicitly open case: clique trees with a given zero forcing number when blocks of size 2 are allowed.
Core Claim
Let $G$ be a graph with a designated root vertex $r$. Let $B$ be the adjacency matrix of $G - r$ and $a$ the 0/1 vector of the neighbours of $r$. For real $x$ larger than the spectral radius of $G-r$, define the branch function
$$F_{(G,r)}(x) = a^{T}(xI - B)^{-1}a ,$$
which by the Schur complement equals $x - \varphi_G(x)/\varphi_{G-r}(x)$, where $\varphi$ is the characteristic polynomial. $F$ is positive, decreasing, and rational with integer coefficients. The spectral radius $\rho(G)$ is the unique $x > \rho(G-r)$ with $F_{(G,r)}(x) = x$. If rooted graphs $(G_1,r),\dots,(G_m,r)$ are glued at their common root, the block structure of $B$ gives
$$F_{G_1\circ\cdots\circ G_m}(x) = \sum_{i=1}^{m} F_{(G_i,r)}(x).$$
The second ingredient covers a block hanging below the root, for example a clique $K_s$. Eliminating each subtree hanging from a non-root vertex $v$ of the block replaces it by the diagonal term $F_v(x)$ at $v$. For a clique, Sherman–Morrison then gives the parent's branch function in closed form, and that function is increasing in each child's $F_v$. The same holds for complete bipartite blocks.
The consequence is a substitution lemma. Suppose a branch $H$ dominates a branch $H'$ pointwise on $[\lambda^\ast,\infty)$, where $\lambda^\ast$ is any proven lower bound on the optimum. Suppose also that $H$ has the same order, the same contribution to the constraint, and the same boundary state as $H'$. Then swapping $H'$ for $H$ anywhere in a block graph cannot decrease $\rho$ and leaves the constraint unchanged. Edge-shifting surgery needs a global argument that each move preserves the invariant. Substitution needs only the local bookkeeping that the induction community already does.
The claim is therefore threefold. First, for any invariant computed by a finite-state recursion over rooted block-cut trees, maximizing $\rho$ reduces to computing the pointwise upper envelope of branch functions indexed by (order, invariant value, boundary state). Second, for natural invariants these envelopes stay small. Third, once the envelopes stabilize, an induction on the number of blocks proves the extremal graph for all $n$, not just for "sufficiently large" $n$. Spectral minimization, which the file notes is open for both the clique-tree and bi-block problems, uses lower envelopes with the same machinery.
Relation to Prior Work
Four papers supply the targets and show how far surgery reaches.
- Dissociation number. Maximization of the spectral radius of block graphs with a given dissociation number finds the star-like maximizer by shifting blocks to a central cut vertex and evaluating an equitable-partition quotient matrix. It explicitly gives no account of how $\rho$ evolves under block grafting, which is exactly what the branch function provides.
- Zero forcing. On the maximum spectral radius of clique trees with a given zero forcing number reduces zero forcing to the static identity $k = n - b$ (zero forcing number equals order minus number of blocks). It then solves a $3\times 3$ quotient matrix. The identity, and with it the proof, breaks once bridges are allowed, which is our main open target.
- Bi-block graphs. On the spectral radius of bi-block graphs with given independence number α is the closest existing work: it does induct on the number of blocks. Its induction carries a scalar comparison specialized to complete bipartite blocks and the independence number. Our hypothesis is function-valued and parametrized by an arbitrary finite-state invariant.
- Minor-free graphs. The spectral radius of minor-free graphs uses induction only inside auxiliary lemmas, while the extremality itself comes from global bounds valid for large $n$.
Three papers supply the inductive method: rooted block-cut-tree induction with boundary bookkeeping.
- Progress towards the two-thirds conjecture on locating-total dominating sets inducts along a rooted block-cut tree to prove $\gamma_t^L \le 2n/3$ for block graphs, where $\gamma_t^L$ is the locating-total domination number.
- On Three Domination-Based Identification Problems in Block Graphs uses a layer function to induct from root blocks down to leaf blocks.
- Locating-dominating partitions for some classes of graphs strengthens the hypothesis, proving the existence of a partition rather than the bare bound.
None of these touch spectra. We reuse their rooting and boundary-state discipline and add the branch function as one more piece of state.
Two lines of work constrain the design. The stability method in Subdivision-free graphs with the maximum spectral radius finds the macroscopic extremal shape but leaves both the threshold $n_0$ and the fine structure of the periphery undetermined. That is the gap that motivates exact, all-$n$ statements. Fully Computer-Assisted Proofs in Extremal Combinatorics shows that metaheuristic search finds constructions but gives no optimality guarantee. It also found that reinforcement learning lost to Tabu search. We therefore do not propose learned search as the engine.
Research Program
Exact branch-function calculus. We will implement branch functions as pairs of integer polynomials. The work has four parts:
- composition rules for vertex gluing, which is addition;
- composition through a clique block and through a complete bipartite block, both in closed form via Sherman–Morrison;
- an exact dominance test, deciding whether $F_H - F_{H'} \ge 0$ on $[\lambda^\ast,\infty)$ by Sturm sequences over the rationals;
- an exact computation of $\rho$ as the largest root of $F(x) = x$.
We will check the calculus against direct eigenvalue computation on every block graph up to 12 vertices.
Invariant recursions. For each constraint we write the finite-state recursion over the rooted block-cut tree and verify it against brute force on all block graphs up to 14 vertices.
- Dissociation number (the largest vertex set inducing maximum degree at most 1). The boundary states record whether the root is outside the set, inside with degree 0, or inside with degree 1.
- Independence number.
- Zero forcing number on block graphs with bridges. We will derive this recursion rather than assume it, and its correctness is a deliverable in its own right.
- Locating-dominating number (a secondary target). The boundary states must also record which separations are still pending across the cut vertex.
Envelope dynamic program. For each tuple (order $n$, invariant value $k$, boundary state $\sigma$) we keep only the branch functions that no other function in the same cell dominates on $[\lambda^\ast,\infty)$. For $\lambda^\ast$ we use the spectral radius of the best graph found so far, which is a valid lower bound on the optimum. Under this pruning, the true maximizer for every $(n,k)$ is computed exactly, not heuristically, up to the largest $n$ at which the envelopes remain small.
From envelopes to theorems. When the surviving branches form a recognizable parametric family, we write a strengthened inductive statement: "for every $(n,k,\sigma)$, the branch function of the family member pointwise dominates every rooted branch." An example family is "one large clique plus triangles plus at most one pendant edge at the root". We then prove the induction step symbolically. Gluing preserves dominance because $F$ is additive, and passing through a block preserves dominance because the block rule is monotone. What remains is a finite set of base-case and exchange inequalities among family members, which the Sturm-sequence checker discharges with exact rational arithmetic. Those certificates can additionally be formalized in Lean, in the spirit of the verification used in Mapping Uncharted Symmetries: Machine Discovery in Combinatorics, if time permits.
Baselines
Exhaustive enumeration (naive reference). We enumerate every block graph of order $n$ by generating block-cut trees, compute $\rho$ numerically, and filter by the invariant. It is the ground truth, and we will run it on the same machine and wall-clock budget as the dynamic program. The dynamic program beats it if three conditions hold. First, it reproduces every enumerated maximizer exactly. Second, it reaches orders at least twice the largest $n$ that enumeration finishes within a fixed 24-hour budget. Third, it produces something enumeration cannot: an all-$n$ proof.
Hand-crafted surgery with quotient matrices (strongest existing method). These are the proofs for dissociation number and for zero-forcing clique trees in the Das–Mohanty and Das papers above. No quantitative metric applies, and no reported result was found on Lacuna for any computational performance figure on these problems. The reference point is the theorems themselves. We match them fairly by requiring that our pipeline, given only the invariant recursion, rederives the extremal graphs $\mathbb{B}_{k,\phi}$ and $K_{2k-n+2}\odot K_3^{(n-k-1)}$, together with the bi-block result $K_{\alpha,k-\alpha}$, with no problem-specific input. Beating this baseline means settling a case the surgery papers list as open: clique trees with bridges under fixed zero forcing number, or minimization of $\rho$ for fixed zero forcing number.
Tabu search (computational baseline). This follows Fully Computer-Assisted Proofs in Extremal Combinatorics, here searching over block graphs with the invariant as a hard constraint. That paper reports results only on Ramsey multiplicity, for example $c_4 < 0.03015$, and no reported result was found on Lacuna for spectral radius of block graphs. We give it the same compute budget. We score both methods on the fraction of $(n,k)$ cells where they find the exact optimum, measured against the dynamic program's certified value.
Scalar-state ablation. This ablation isolates the key ingredient. It runs the same dynamic program but keeps only each branch's own spectral radius, or its branch function evaluated at the single point $\lambda^\ast$. Because $\rho$ of a glued graph is not determined by the children's spectral radii, this variant is unsound. We will count how many of its outputs are wrong. If the count is zero across all tested ranges, the function-valued state is unnecessary in practice, and we would report that honestly.
Why not just…?
Why not just extend the edge-shifting surgery, as the clique-tree paper did? Surgery works when every move provably stays inside the constrained family. For clique trees this followed from $k = n - b$, and the author notes that allowing size-2 blocks destroys that relation. A clever surgery argument for the bridge case may still exist, and this is a real threat. The substitution lemma is effectively a generic, invariant-safe surgery, and the dynamic program tells the surgeon which substitutions to attempt. If a hand proof appears first, our method is still the only one that also yields minimizers and arbitrary finite-state invariants without new ideas for each case.
Why not just apply the stability method? Stability, as in the subdivision-free and minor-free papers, establishes the shape for unquantified large $n$ and leaves the fine structure "saturated". Block graphs under these invariants are exactly the regime where all-$n$ answers are wanted. Our proofs hold from the base case upward, which the stability method cannot provide.
Why not just enumerate small cases, guess the pattern, and prove it by hand? Enumeration does generate conjectures well, and we use it as a baseline. The difficult step is the proof, though, and enumeration offers no induction hypothesis. The envelope dynamic program outputs the strengthened statement directly, namely which branch dominates in each boundary state. The bridge-zero-forcing experiment tests whether that statement is simple enough to prove.
Why not use a language model or neural prover to write the induction? The evidence in the file is discouraging. On Can Large Language Models Analyze Graphs like Professionals?, GPT-4o reaches 36.3% zero-shot and about 32% on multi-step tasks. On INT: An Inequality Benchmark for Evaluating Generalization in Theorem Proving, Transformer provers drop 66.8% on unseen axiom combinations. Our inequalities are univariate rational dominance statements, which Sturm sequences decide exactly, so learned guidance is not needed.
Proposed Experiments
Calibration. We will validate the calculus against brute-force eigenvalues on all block graphs up to 12 vertices, and each invariant recursion against brute force up to 14 vertices.
Rediscovery. We will run the envelope dynamic program on the three solved problems: dissociation number, zero-forcing clique trees, and bi-block graphs with given independence number. Success means recovering each published extremal family exactly and producing the corresponding all-$n$ inductive certificate automatically.
Primary open problem: zero forcing with bridges. We will compute certified maximizers for block graphs with bridges and given zero forcing number for every feasible $(n,k)$ up to the largest reachable order. We record envelope sizes per cell, aiming for at least $n = 30$. We then attempt the strengthened induction. Two outcomes count as decisive. The first is a theorem valid for all $n$. The second is a documented failure in which envelope sizes grow with $n$, which would show that this invariant has no small inductive spectral hypothesis. Both are informative, and the growth curve of envelope size against $n$ is the main empirical quantity.
Secondary targets. We will run the same pipeline for spectral minimization of zero-forcing clique trees and for maximization under the locating-dominating number. The second extends the block-graph induction of the identification papers into spectral territory and tests whether richer boundary states keep the envelopes tractable.
Ablation and comparison. We will report the scalar-state ablation's error count and Tabu search's exact-hit rate in every cell where the dynamic program has certified the optimum.
References
- Maximization of the spectral radius of block graphs with a given dissociation number
- On the maximum spectral radius of clique trees with a given zero forcing number
- On the spectral radius of bi-block graphs with given independence number $α$
- The spectral radius of minor-free graphs
- Progress towards the two-thirds conjecture on locating-total dominating sets
- On Three Domination-Based Identification Problems in Block Graphs
- Locating-dominating partitions for some classes of graphs
- Subdivision-free graphs with the maximum spectral radius
- Fully Computer-Assisted Proofs in Extremal Combinatorics
- Mapping Uncharted Symmetries: Machine Discovery in Combinatorics
- Can Large Language Models Analyze Graphs like Professionals? A Benchmark, Datasets and Models
- INT: An Inequality Benchmark for Evaluating Generalization in Theorem Proving