arxiv: 2604.24165 · v1 · submitted 2026-04-27 · 🧮 math.CO · cs.DM· math.SP

Recognition: unknown

Permanental Energy of Graphs

Priyanshu Pant , Ranveer Singh

Authors on Pith no claims yet

Pith reviewed 2026-05-08 02:44 UTC · model grok-4.3

classification 🧮 math.CO cs.DMmath.SP

keywords permanental energypermanental polynomialgraph energylower boundstar graphadjacency matrixpermanentspectral radius

0 comments

The pith

The permanental energy of any m-edge graph is at least 2√m, with equality only for stars plus isolated vertices.

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

The paper defines the permanental energy of a graph G as the sum of the absolute values of the roots of its permanental polynomial, which is the permanent of xI minus the adjacency matrix. It proves that this quantity is always at least 2 times the square root of the number of edges m. The bound is sharp, and equality holds precisely when the graph is a star together with some isolated vertices. A reader would care because the result gives a simple, universal inequality that characterizes the extremal graphs in terms of their edge count.

Core claim

For every m-edge graph G, the permanental energy E_per(G) defined as the sum of absolute values of the roots of per(xI - A(G)) satisfies E_per(G) ≥ 2√m, with equality if and only if G is a star together with isolated vertices. The paper also proves the general upper bound E_per(G) ≤ n ρ(G) where ρ(G) is the spectral radius, and examines the quantity on several graph families.

What carries the argument

The permanental energy E_per(G) = sum |μ_i| where μ_i are the roots of the permanental polynomial π(G,x) = per(xI - A(G)); this sum is bounded from below using the number of edges m.

If this is right

The lower bound is achieved precisely when the graph consists of a single star and any number of isolated vertices.
For any graph the permanental energy is at most the number of vertices times the spectral radius of the adjacency matrix.
The permanental energy can be evaluated or bounded explicitly on families such as complete graphs, paths, and cycles.

Where Pith is reading between the lines

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

The same permanent-based bound might be adapted to other matrix polynomials or immanants to produce analogous energy-like invariants.
Because the permanent counts perfect matchings, the inequality may imply relations between the number of matchings and the distribution of roots in the permanental polynomial.

Load-bearing premise

The equality holds uniquely for stars plus isolates because their adjacency matrices produce permanents that achieve the minimal possible sum of absolute roots among all graphs with the same number of edges.

What would settle it

An explicit m-edge graph that is not a star plus isolated vertices but has permanental energy strictly less than 2√m, or equal to 2√m without matching that structure, would disprove the claim.

read the original abstract

For a simple graph $G$ with adjacency matrix $A(G)$, let $\pi(G,x):=\mathrm{per}(xI-A(G))$ be its permanental polynomial with roots $\mu_1,\ldots,\mu_n \in \mathbb{C}$, and define the permanental energy $E_{\mathrm{per}}(G):=\sum_{i=1}^n |\mu_i|$. We prove a sharp universal lower bound: for every $m$-edge graph $G$, $E_{\mathrm{per}}(G) \ge 2\sqrt{m}$, with equality if and only if $G$ is a star together with isolated vertices. We also prove the general upper bound $E_{\mathrm{per}}(G) \le n\rho(G)$, where $\rho(G)$ is the spectral radius, and we study $E_{\mathrm{per}}(G)$ on several graph families.

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

The paper defines permanental energy and proves a sharp lower bound of 2√m with equality exactly for stars plus isolated vertices.

read the letter

The key thing to know is that this paper defines permanental energy via the roots of the permanental polynomial and proves a sharp lower bound E_per(G) ≥ 2√m with equality if and only if G is a star plus isolated vertices. The definition itself is new, and the bound with its equality characterization appears to be a fresh result in the area of graph energies. The authors also establish an upper bound in terms of the number of vertices and the spectral radius, and they calculate the invariant explicitly for some common graph families. What works well is the lower bound. The relations from the permanental polynomial coefficients give sum of roots zero and sum of pairwise products equal to m, hence sum of squares equal to -2m. This, combined with the zero-sum condition on real and imaginary parts, leads to the minimal sum of absolute values being 2√m, achieved exactly when the polynomial is x^{n-2}(x^2 + m). Only stars plus isolates have this form because other graphs produce nonzero contributions from longer cycles or disjoint transpositions in the permanent expansion. The upper bound is less novel since it follows from known permanent-spectral comparisons. The family studies are standard calculations that confirm the bound but do not add much depth. This paper is for specialists in algebraic graph theory interested in polynomial invariants and energy concepts. A reader looking for new bounds on graph polynomials would get value from the sharp inequality and the precise equality case. It deserves a serious referee because the central claim is well-supported by the coefficient analysis and the equality condition is cleanly stated. I would send it out for peer review.

Referee Report

2 major / 2 minor

Summary. The manuscript defines the permanental energy E_per(G) as the sum of absolute values of the roots of the permanental polynomial per(xI - A(G)). It proves the sharp lower bound E_per(G) ≥ 2√m for every m-edge graph G, with equality if and only if G is a star plus isolated vertices. It also establishes the general upper bound E_per(G) ≤ n ρ(G) and examines the invariant on several graph families.

Significance. The lower bound supplies a parameter-free, sharp inequality linking permanental energy directly to edge count, with a clean equality characterization that isolates a specific extremal class. The derivation via Vieta formulas on the permanental polynomial and L1-norm minimization on zero-mean sequences is elegant and self-contained. The upper bound is a straightforward consequence of known permanent-spectral comparisons. Family computations add concrete illustrations. These results strengthen the toolkit of permanental graph invariants.

major comments (2)

[§3] §3, proof of Theorem 3.1: the equality case requires showing that only stars-plus-isolates yield the permanental polynomial x^{n-2}(x^2 + m). Confirm that the expansion of per(A) for any other m-edge graph necessarily includes nonzero terms from permutations with support on three or more vertices (longer cycles or multiple disjoint transpositions), and that these terms prevent the root set from being exactly {i√m, -i√m, 0, …, 0}.
[Theorem 4.2] Theorem 4.2 (upper bound): the inequality E_per(G) ≤ n ρ(G) is derived from the known comparison per(A) ≤ n! ρ^n or similar; state explicitly which permanent-spectral inequality is invoked and whether equality can hold for any non-trivial graphs.

minor comments (2)

[Introduction] Introduction: the definition of permanental energy should cite prior work on permanental polynomials (e.g., the survey by Merris or related papers) to situate the new invariant.
[Section 5] Section 5 (family computations): tables listing E_per values should include the exact edge count m for each graph to allow direct verification of the lower bound.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation and the helpful suggestions for improving the exposition. We address the two major comments point by point below and will incorporate the requested clarifications into the revised manuscript.

read point-by-point responses

Referee: [§3] §3, proof of Theorem 3.1: the equality case requires showing that only stars-plus-isolates yield the permanental polynomial x^{n-2}(x^2 + m). Confirm that the expansion of per(A) for any other m-edge graph necessarily includes nonzero terms from permutations with support on three or more vertices (longer cycles or multiple disjoint transpositions), and that these terms prevent the root set from being exactly {i√m, -i√m, 0, …, 0}.

Authors: We agree that the equality case merits a more explicit verification. In the revised manuscript we will expand the argument in the proof of Theorem 3.1 by showing that per(xI − A(G)) equals x^{n−2}(x^2 + m) if and only if G is a star plus isolated vertices. Concretely, we will note that any graph containing a cycle of length at least 3 produces a nonzero contribution to the coefficient of x^{n−3} (from the corresponding 3-cycle permutation, whose product introduces a factor (−1)^3), while any graph containing two or more vertex-disjoint edges produces a nonzero contribution to the coefficient of x^{n−4} (from the product of two disjoint transpositions). These extra terms alter the polynomial, so the roots cannot be precisely {i√m, −i√m, 0, …, 0} and the permanental energy is therefore strictly larger than 2√m. revision: yes
Referee: [Theorem 4.2] Theorem 4.2 (upper bound): the inequality E_per(G) ≤ n ρ(G) is derived from the known comparison per(A) ≤ n! ρ^n or similar; state explicitly which permanent-spectral inequality is invoked and whether equality can hold for any non-trivial graphs.

Authors: We will revise the proof of Theorem 4.2 to state explicitly that the bound follows from the known comparison that every permanental root μ_i satisfies |μ_i| ≤ ρ(G), which is a consequence of the inequality per(B) ≤ n! ‖B‖^n applied to suitable shifts of the adjacency matrix (or, equivalently, from the fact that the permanental radius is at most the ordinary spectral radius). We will also add a short remark on equality: the bound E_per(G) = n ρ(G) holds with equality for the empty graph (both sides zero) and for the single-vertex graph, but for any graph with at least one edge the inequality is strict, since not all permanental roots attain modulus ρ(G). revision: yes

Circularity Check

0 steps flagged

No circularity; lower bound derived from Vieta and root inequalities

full rationale

The claimed lower bound E_per(G) ≥ 2√m follows from applying Vieta's formulas to the permanental polynomial π(G,x) = per(xI - A(G)), which yields sum μ_i = 0 and sum_{i<j} μ_i μ_j = m for any graph with m edges. These relations imply a fixed sum of squares on the roots, from which the L1 norm sum |μ_i| is bounded below by 2√m via a standard inequality on zero-mean sequences (with equality only for the specific root configuration x^{n-2}(x² + m)). This configuration is realized precisely by stars plus isolates, as other graphs contribute nonzero permanent terms from longer cycles or multiple transpositions. No parameters are fitted, no self-definitions or self-citations are load-bearing, and the steps are independent of the target inequality.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper introduces the definition of permanental energy but rests on standard definitions of the permanent and adjacency matrix; no free parameters are fitted and no new entities are postulated.

axioms (2)

standard math The permanent of an n×n matrix is the sum over all permutations of the product of the selected entries.
Used to define the permanental polynomial π(G,x).
domain assumption The roots of the permanental polynomial are complex numbers whose absolute values can be summed to form an energy-like invariant.
Directly invoked in the definition of E_per(G).

pith-pipeline@v0.9.0 · 5444 in / 1314 out tokens · 53981 ms · 2026-05-08T02:44:10.591135+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

28 extracted references

[1]

Computing the permanental polynomials of bipartite graphs by pfaffian orientation.Discrete Applied Mathematics, 160(13):2069–2074, 2012

2069
[2]

On spectrum and per-spectrum of graphs.Publ

Mieczyslaw Borowiecki. On spectrum and per-spectrum of graphs.Publ. Inst. Math. (Beograd), 38:31–33, 1985

1985
[3]

Brenner and Richard A

Joseph L. Brenner and Richard A. Brualdi. Eigenschaften der Perma- nentefunktion.Archiv der Mathematik, 18:585–586, 1967. 13

1967
[4]

Bunch and John E

James R. Bunch and John E. Hopcroft. Triangular factorization and inversion by fast matrix multiplication.Mathematics of Computation, 28(125):231–236, 1974

1974
[5]

Academic Press, New York, 1980

Dragoš Cvetković, Michael Doob, and Horst Sachs.Spectra of Graphs: Theory and Application. Academic Press, New York, 1980

1980
[6]

Highly unique network descriptors based on the roots of the permanental polynomial.Information Sci- ences, 408:176–181, 2017

Matthias Dehmer, Frank Emmert-Streib, Bo Hu, Yongtang Shi, Mon- ica Stefu, and Shailesh Tripathi. Highly unique network descriptors based on the roots of the permanental polynomial.Information Sci- ences, 408:176–181, 2017

2017
[7]

I. S. Gradshteyn and I. M. Ryzhik.Table of Integrals, Series, and Products. Academic Press, 8 edition, 2014

2014
[8]

Graham, Donald E

Ronald L. Graham, Donald E. Knuth, and Oren Patashnik.Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley, 2 edition, 1994

1994
[9]

The energy of a graph.Chemical Physics Letters, 57:358– 361, 1978

Ivan Gutman. The energy of a graph.Chemical Physics Letters, 57:358– 361, 1978

1978
[10]

Ivan Gutman and Gordon G. Cash. Relations between the permanen- tal and characteristic polynomials of fullerenes and benzenoid hydro- carbons.MATCH Communications in Mathematical and in Computer Chemistry, 45:55–70, 2002

2002
[11]

An efficient algorithm for computing permanental polynomials of graphs.Computer Physics Com- munications, 175(3):196–203, 2006

Yan Huo, Heng Liang, and Fengshan Bai. An efficient algorithm for computing permanental polynomials of graphs.Computer Physics Com- munications, 175(3):196–203, 2006

2006
[12]

Chemical graph theory

Darko Kasum, Nenad Trinajstić, and Ivan Gutman. Chemical graph theory. III. on the permanental polynomial.Croatica Chemica Acta, 54(3):321–328, 1981

1981
[13]

The permanental polynomials of certain graphs.MATCH Communications in Mathematical and in Computer Chemistry, 68(3):871–888, 2012

Wei Li and Heping Zhang. The permanental polynomials of certain graphs.MATCH Communications in Mathematical and in Computer Chemistry, 68(3):871–888, 2012

2012
[14]

Springer, New York, 2012

Xueliang Li, Yongtang Shi, and Ivan Gutman.Graph Energy. Springer, New York, 2012

2012
[15]

Computing the permanental polynomial of C60 in parallel.MATCH Communications in Mathemat- ical and in Computer Chemistry, 60:349–358, 2008

Heng Liang, Hui Tong, and Fengshan Bai. Computing the permanental polynomial of C60 in parallel.MATCH Communications in Mathemat- ical and in Computer Chemistry, 60:349–358, 2008. 14

2008
[16]

Liu and H

S. Liu and H. Zhang. On the characterizing properties of the per- manental polynomials of graphs.Linear Algebra and its Applications, 438(1):157–172, 2013

2013
[17]

Enumeration of copermanental graphs

Shunyi Liu and Jinjun Ren. Enumeration of copermanental graphs. 2015

2015
[18]

American Mathematical Society, 1966

Morris Marden.Geometry of Polynomials, volume 3 ofMathematical Surveys. American Mathematical Society, 1966

1966
[19]

Pólya’s permanent problem.The Electronic Journal of Combinatorics, 11(1):R79, 2004

William McCuaig. Pólya’s permanent problem.The Electronic Journal of Combinatorics, 11(1):R79, 2004

2004
[20]

Rebman, and William Watkins

Russell Merris, Kenneth R. Rebman, and William Watkins. Permanen- tal polynomials of graphs.Linear Algebra and its Applications, 38:273– 288, 1981

1981
[21]

Cambridge University Press, 1984

Henryk Minc.Permanents, volume 6 ofEncyclopedia of Mathematics and its Applications. Cambridge University Press, 1984

1984
[22]

A Perma- nental Analog of the Rank-Nullity Theorem for Symmetric Matrices

Priyanshu Pant, Surabhi Chakrabartty, and Ranveer Singh. A Perma- nental Analog of the Rank-Nullity Theorem for Symmetric Matrices. 364:70:1–70:12, 2026

2026
[23]

Aufgabe 424.Archiv der Mathematik und Physik, 20:271, 1913

George Pólya. Aufgabe 424.Archiv der Mathematik und Physik, 20:271, 1913

1913
[24]

Richard P. Stanley. A bound on the spectral radius of graphs withe edges.Linear Algebra and its Applications, 87–88:267–271, 1987

1987
[25]

Generalized matrix functions and the graph isomorphism problem.SIAM Journal on Applied Mathematics, 16(3):520–526, 1968

James Turner. Generalized matrix functions and the graph isomorphism problem.SIAM Journal on Applied Mathematics, 16(3):520–526, 1968

1968
[26]

Leslie G. Valiant. The complexity of computing the permanent.Theo- retical Computer Science, 8(2):189–201, 1979

1979
[27]

On the permanental nullity and matching number of graphs.Linear and Multilinear Algebra, 66(3):516– 524, 2018

Tingzeng Wu and Hong-Jian Lai. On the permanental nullity and matching number of graphs.Linear and Multilinear Algebra, 66(3):516– 524, 2018. A Proof of Theorem 4.6 This appendix proves Theorem 4.6. We use the following explicit expression forπ(C n, x)due to Li and Zhang. 15 Theorem A.1([13]).Forn≥3, π(Cn, x) =    nY t=1 x+ 2i sin (2t−1)π n ,if...

2018
[28]

Take y= 1 + √ 2 =e a and write λ= exp a+ 2πik n , k= 0,1, . . . , n−1. Finally, x=λ− 1 λ = exp a+ 2πik n −exp − a+ 2πik n = 2 sinh a+ 2πik n , which gives the claimed roots. Corollary A.6.Ifnis odd, then Eper(Cn) = 4 π n+o(n) (n→ ∞, nodd). Proof.Letu:=a/nandθ k := 2πk/n. By Lemma A.5, µk = 2 sinh(u+ iθk). Using|sinh(u+ iθ)| 2 = sinh2 u+ sin 2 θ, we obtain...