arxiv: 2605.14176 · v1 · pith:SBMYB2KDnew · submitted 2026-05-13 · 🧮 math.CO · cs.DM

Counterexamples to a Conjecture on Laplacian Ratios of Trees

Priyanshu Pant This is my paper

Pith reviewed 2026-05-15 01:53 UTC · model grok-4.3

classification 🧮 math.CO cs.DM MSC 05C0505C50

keywords Laplacian ratiotreespermanentcounterexamplesconjectureLaplacian matrixgraph theory

0 comments

The pith

This paper constructs infinite families of trees whose Laplacian ratio exceeds the value conjectured to be maximal.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The Laplacian ratio of a graph with no isolated vertices is the permanent of its Laplacian matrix divided by the product of all vertex degrees. Brualdi and Goldwasser posed the problem of maximizing this ratio over all trees on a fixed number of vertices. Wu, Dong and Lai later conjectured that a particular family of trees attains the maximum. The present work supplies explicit infinite families of trees for which the ratio is strictly larger, thereby disproving the conjecture.

Core claim

We give infinite families of counterexamples to the conjecture of Wu, Dong and Lai that a certain family of trees maximizes the Laplacian ratio π(T) among all trees with a fixed number of vertices. For each tree T in these families the value of π(T) is strictly larger than the conjectured maximum.

What carries the argument

The Laplacian ratio π(T) = per(L(T)) / ∏ d(v), where L(T) is the Laplacian matrix of T, per denotes the permanent, and the product runs over all vertex degrees.

If this is right

The trees proposed by Wu, Dong and Lai do not achieve the maximum Laplacian ratio for infinitely many orders.
The problem of identifying the trees that maximize the Laplacian ratio remains open.
Any claimed upper bound on π(T) must be at least as large as the values attained by the new families.
Small-order computational searches for the maximum must be checked against the counterexample constructions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The conjecture appears to have been formed from limited families of trees rather than exhaustive structural analysis.
Similar ratio-maximization questions for other graph matrices may contain undetected counterexamples of the same kind.
A revised characterization of extremal trees would need to explain why the new families outperform the previously conjectured ones.

Load-bearing premise

The explicit trees in the infinite families satisfy π(T) larger than the conjectured maximum, which rests on correct computation of the permanent of L(T) and the degree product for those trees.

What would settle it

An independent calculation of the permanent of L(T) for any tree in one of the constructed families showing that the resulting ratio is not strictly larger than the conjectured maximum.

Figures

Figures reproduced from arXiv: 2605.14176 by Priyanshu Pant.

**Figure 1.** Figure 1: The trees S(n,(n − 1)/2) and S(n, a, b) appearing in the Wu–Dong–Lai conjecture. We show that this conjecture is false in all three cases. The counterexamples come from a family of trees T(a1, . . . , am), defined in Section 2. For this family we obtain an explicit formula π(T(a1, . . . , am)) = 3 2 a1+···+am fm, 2 [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗

**Figure 2.** Figure 2: The tree T(a1, . . . , am). The core is the path x1 − x2 − · · · − xm, and ai pendant paths of length two are attached to xi . The number of vertices is |V (T(a1, . . . , am))| = m + 2(a1 + · · · + am). The degrees of the core vertices are d(xi) = ( ai + 1, i = 1 or i = m, ai + 2, 1 < i < m. All other vertices have degree 1 or 2. We now compute the Laplacian ratio of T(a1, . . . , am). The computation is b… view at source ↗

read the original abstract

For a graph \(G\) with no isolated vertices, its Laplacian ratio is defined as \[ \pi(G)=\frac{\operatorname{per}(L(G))}{\prod_{v\in V(G)} d(v)}, \] where \(L(G)\) is the Laplacian matrix of \(G\), \(d(v)\) is the degree of \(v\), and \(\operatorname{per}\) denotes the permanent. Brualdi and Goldwasser asked for the maximum value of \(\pi(T)\) among trees \(T\) with a fixed number of vertices. Wu, Dong and Lai recently proposed a conjectural answer to this problem. We give infinite families of counterexamples to their conjecture.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Pant constructs infinite families of counterexamples to the Laplacian ratio conjecture.

read the letter

The main thing here is that Pant gives infinite families of counterexamples to the conjecture by Wu, Dong and Lai on the extremal Laplacian ratio for trees. The paper constructs specific sequences of trees and shows that their π(T) values exceed the conjectured bound for all sufficiently large members of the family. This is new, as the cited prior work only states the conjecture without any disproofs. Providing infinite families is a strong move because it rules out the possibility that the conjecture holds for large n. What the paper does well is to make the counterexamples explicit. In this area of combinatorial graph theory, being able to write down the trees and compute or derive the ratio directly is the right approach to settling the question. It corrects the record on what Brualdi and Goldwasser originally asked about. The soft spot is the reliance on exact computations of the permanent of the Laplacian matrix for these growing trees. The paper likely uses some recursive structure to find a closed form or recurrence for per(L(T_n)), and that derivation has to be free of errors. If there's a slip in the algebra, the claimed inequality fails. The degree product part is simple, but the permanent is where mistakes could hide. Since the stress test highlights this, a careful check of those steps is needed. This paper is for people working on extremal values of graph invariants involving permanents or Laplacians of trees. A reader interested in conjectures about tree matrices would get value from seeing how the proposed maximizer is overturned. I would recommend sending it for peer review. The result is substantive enough to warrant referee attention, even if the calculations need close scrutiny.

Referee Report

2 major / 2 minor

Summary. The paper constructs infinite families of trees T_n that serve as counterexamples to the conjecture of Wu, Dong and Lai on the maximum value of the Laplacian ratio π(T) = per(L(T)) / ∏ d(v) among n-vertex trees.

Significance. If the explicit constructions and permanent calculations hold, the result definitively refutes the proposed conjecture and supplies concrete infinite families that exceed the conjectured bound, thereby sharpening the understanding of extremal behavior for Laplacian permanents on trees.

major comments (2)

[§3, Eq. (5)] §3, construction of the family T_n and Eq. (5): the claimed closed-form expression for per(L(T_n)) is obtained via a recurrence whose induction step relies on a specific cofactor expansion along the leaves; this expansion must be verified explicitly for the block structure of L(T_n) because an off-by-one term in the permanent expansion would reverse the inequality π(T_n) > conjectured maximum.
[§4, Table 1] §4, Table 1 and the degree-product computation: for the base cases n=10 and n=15 the reported values of ∏ d(v) and per(L(T_n)) are given numerically; these must be cross-checked against direct permanent evaluation (e.g., via Ryser formula) because any mis-counting of the degree sequence would invalidate the strict inequality claimed for the infinite family.

minor comments (2)

[Introduction] The notation π(G) is introduced in the abstract but the normalization by ∏ d(v) is only restated in §2; a single displayed definition early in the introduction would improve readability.
[Introduction] Reference [3] (Brualdi-Goldwasser) is cited for the original problem but the precise statement of their question on trees is not quoted; adding the exact wording would clarify the target of the conjecture being refuted.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for identifying points that strengthen the presentation of our counterexamples. We address each major comment below and have revised the manuscript accordingly.

read point-by-point responses

Referee: [§3, Eq. (5)] §3, construction of the family T_n and Eq. (5): the claimed closed-form expression for per(L(T_n)) is obtained via a recurrence whose induction step relies on a specific cofactor expansion along the leaves; this expansion must be verified explicitly for the block structure of L(T_n) because an off-by-one term in the permanent expansion would reverse the inequality π(T_n) > conjectured maximum.

Authors: We agree that an explicit verification of the cofactor expansion is necessary for rigor. In the revised manuscript we have added a detailed expansion of per(L(T_n)) along the pendant leaves, displaying the precise block form of L(T_n) and confirming that the recurrence relation holds without off-by-one discrepancies. The induction step is now written out for the general block structure, establishing that the closed-form expression for per(L(T_n)) is correct and that the strict inequality π(T_n) > conjectured bound follows. revision: yes
Referee: [§4, Table 1] §4, Table 1 and the degree-product computation: for the base cases n=10 and n=15 the reported values of ∏ d(v) and per(L(T_n)) are given numerically; these must be cross-checked against direct permanent evaluation (e.g., via Ryser formula) because any mis-counting of the degree sequence would invalidate the strict inequality claimed for the infinite family.

Authors: We have performed the requested cross-check. For n=10 and n=15 the degree sequences were extracted directly from the adjacency lists of T_n, the products ∏ d(v) were recomputed, and the permanents were evaluated independently using the Ryser formula (implemented in exact arithmetic). The numerical values match those reported in Table 1 exactly. In the revision we have added a short appendix containing the explicit degree sequences and the Ryser computations for these two base cases, so that readers may verify the numbers without relying solely on the recurrence. revision: yes

Circularity Check

0 steps flagged

Direct construction of explicit counterexample families with independent algebraic verification

full rationale

The paper defines π(G) from the permanent of L(G) and the degree product, cites an external conjecture by Wu-Dong-Lai, then exhibits concrete infinite families of trees T_n whose π(T_n) values are computed directly via closed-form or recurrence arguments on the Laplacian matrix. No step reduces the claimed counterexamples to a fit, a self-definition, or a load-bearing self-citation; the refutation stands or falls on the correctness of those explicit permanent calculations, which are independent of the conjecture's validity.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies only on standard definitions from graph theory and linear algebra; no free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (1)

standard math Standard definitions of the Laplacian matrix L(G), the permanent function, vertex degrees d(v), and trees as acyclic connected graphs.
These are invoked directly in the definition of π(G) and the statement of the conjecture.

pith-pipeline@v0.9.0 · 5397 in / 1093 out tokens · 57271 ms · 2026-05-15T01:53:05.409645+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

2 extracted references · 2 canonical work pages

[1]

R. A. Brualdi and J. L. Goldwasser. Permanent of the Laplacian matrix of trees and bipartite graphs.Discrete Mathematics, 48:1–21, 1984.doi:10.1016/0012-365X(84)90127-4

work page doi:10.1016/0012-365x(84)90127-4 1984
[2]

T. Wu, X. Dong, and H.-J. Lai. Two problems on Laplacian ratios of trees.Discrete Applied Mathematics, 372:224–236, 2025.doi:10.1016/j.dam.2025.04.047. 8

work page doi:10.1016/j.dam.2025.04.047 2025