pith. sign in

arxiv: 2606.11547 · v1 · pith:N3FBX4MCnew · submitted 2026-06-10 · 🧮 math.CO

Multiplicity of Laplacian eigenvalue 1 of a graph

Yuhao Zhou , Fenglei Tian This is my paper

Pith reviewed 2026-06-27 09:40 UTC · model grok-4.3

classification 🧮 math.CO
keywords Laplacian eigenvalueeigenvalue multiplicityreduced graphpendant vertexquasi-pendant vertexBetti numberextremal treeextremal graph
0
0 comments X

The pith

Reduced trees on n≥7 vertices have Laplacian eigenvalue 1 multiplicity at most (n-5)/6, and connected reduced graphs have multiplicity at most c+(n-2)/4 with c the first Betti number.

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

The paper establishes upper bounds on the multiplicity of Laplacian eigenvalue 1 in reduced graphs, where the number of pendant vertices equals the number of quasi-pendant vertices. It proves that reduced trees meeting the stated structural conditions satisfy m_L(T)(1) ≤ (n-5)/6 and identifies the trees that achieve equality. For general connected reduced graphs the multiplicity is bounded by the first Betti number plus (n-2)/4, again with equality cases fully characterized. These bounds are obtained after applying reduction operations that leave the multiplicity unchanged, allowing the analysis to focus on the reduced forms.

Core claim

For a reduced tree T on n(≥7) vertices with each quasi-pendant vertex of degree 2 and without pendant path P3, m_L(T)(1)≤(n-5)/6 and the extremal trees attaining the upper bound are determined completely. In addition, for an arbitrary connected reduced graph G with order n≥6 and size m, with c=m-n+1 the first Betti number, m_L(G)(1)≤c+(n-2)/4 and the extremal graphs attaining the upper bound are characterized completely.

What carries the argument

The reduction operation that converts any graph to an equivalent reduced graph while preserving m_L(1), together with the invariance of m_L(1) under deletion of a pendant path P3.

If this is right

  • Any graph's multiplicity of Laplacian eigenvalue 1 can be read off from its reduced form.
  • The maximum multiplicity grows linearly with order in trees and linearly with both order and number of independent cycles in general graphs.
  • The extremal trees and graphs are completely classified, so the bound is sharp.
  • Deleting pendant P3 paths or performing the reduction leaves the multiplicity unchanged, so the bounds apply to the original graphs as well.

Where Pith is reading between the lines

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

  • The same reduction technique could be applied to bound multiplicities of other Laplacian eigenvalues if analogous invariance properties hold.
  • The additive contribution of the Betti number suggests that each independent cycle can increase the multiplicity by a fixed amount independent of the tree-like parts.
  • Direct computation of the Laplacian spectrum on small reduced graphs would provide an immediate numerical check of the stated inequalities.
  • The extremal constructions may serve as building blocks for graphs that maximize the multiplicity for a given order and number of cycles.

Load-bearing premise

The reduction operation that produces a reduced graph preserves the multiplicity of Laplacian eigenvalue 1.

What would settle it

A single reduced tree on seven or more vertices, each quasi-pendant vertex of degree exactly 2 and no pendant P3, whose Laplacian matrix has eigenvalue-1 multiplicity strictly larger than (n-5)/6.

Figures

Figures reproduced from arXiv: 2606.11547 by Fenglei Tian, Yuhao Zhou.

Figure 1
Figure 1. Figure 1: An example of doing reduction operation on a graph. [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The extreme graph in Theorem 1.1. Apart from trees, the multiplicity of Laplacian eigenvalue 1 of a unicyclic graph was also investigated. Wen and Huang [13] proved that mL(G) (1) ≤ n − 2 for a unicyclic graph G of order n. Tian and Wong [10] obtained mL(G) (1) ≤ n 4 for a reduced unicyclic graph G without P 3 . To generalize these results, we further concentrate on mL(G) (1) for an arbitrary reduced graph… view at source ↗
Figure 3
Figure 3. Figure 3: The trees belong to Ω with order less than 12. [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The graphs G1 ∼ G6 with the dashed cycle meaning the remaining part. For this situation, we consider the graph G1 − exy, which is a reduced tree clearly. Then by Lemmas 2.1 and 2.5, we get mL(G1) (1) ≤ 1 + mL(G1−exy) (1) ≤ 1 + n − 2 4 . (2) Actually, mL(G1) (1) cannot attain the upper bound. If |G1| = 6, then it is not hard to see that mL(G1) (1) = 0 < 1 + n−2 4 = 2. Now, let |G1| ≥ 7 and suppose for a con… view at source ↗
read the original abstract

Let $G$ be a graph with $p(G)$ pendant vertices and $q(G)$ quasi-pendant vertices. Denote by $m_{L(G)}(\lambda)$ the multiplicity of $\lambda$ as a Laplacian eigenvalue of $G$. A graph $G$ is called reduced, if $p(G)=q(G)$. It is known that deleting a pendant path $P_3$ from a graph $G$ cannot change $m_{L(G)}(1)$. By the reduction operation for a graph (defined by Tian and Wong, 2026), we could turn to the reduced graphs with each quasi-pendant vertex of degree 2 to investigate $m_{L(G)}(1)$. Then let $T$ be a reduced tree on $n(\geq 7)$ vertices with each quasi-pendant vertex of degree 2 and without pendant path $P_3$. We first prove that \begin{equation*} m_{L(T)}(1)\leq \frac{n-5}{6} \end{equation*} and the extremal trees attaining the upper bound are determined completely. In addition, let $G$ be an arbitrary connected reduced graph with order $n\geq 6$ and size $m$. Denote by $c=m-n+1$ the first Betti number of $G$, then we obtain \begin{equation*} m_{L(G)}(1)\leq c+\frac{n-2}{4}, \end{equation*} and the extremal graphs attaining the upper bound are characterized completely.

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.

Referee Report

0 major / 2 minor

Summary. The manuscript studies the multiplicity m_L(G)(1) of the Laplacian eigenvalue 1. A graph is reduced if p(G)=q(G). It is given that deleting a pendant P3 preserves m_L(1) and that the Tian-Wong reduction operation reduces any graph to a reduced graph while preserving m_L(1). For reduced trees T on n≥7 vertices with every quasi-pendant vertex of degree 2 and no pendant P3, the paper proves m_L(T)(1) ≤ (n-5)/6 and completely characterizes the extremal trees. For an arbitrary connected reduced graph G on n≥6 vertices with m edges and cyclomatic number c=m-n+1, it proves m_L(G)(1) ≤ c + (n-2)/4 and completely characterizes the extremal graphs.

Significance. If the proofs hold, the results supply explicit upper bounds together with complete extremal characterizations for m_L(G)(1) on two natural classes of reduced graphs. The tree bound is strictly tighter than the general bound when the extra hypotheses apply. The complete determination of extremal examples is a concrete strength of the work.

minor comments (2)
  1. In the abstract, the sentence beginning 'By the reduction operation...' is slightly awkward; a minor rephrasing would improve readability.
  2. The notation m_L(G)(λ) is introduced without an explicit reference to the Laplacian matrix; a one-sentence reminder in the introduction would help readers outside the immediate area.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of the manuscript, the recognition of the significance of the bounds and extremal characterizations, and the recommendation to accept.

Circularity Check

0 steps flagged

No significant circularity; bounds derived via independent case analysis after reduction

full rationale

The paper invokes the known preservation of m_L(1) under deletion of pendant P3 and under the reduction operation (cited to Tian-Wong 2026) to restrict attention to reduced graphs/trees with specified pendant structure. It then proves the two inequalities by direct structural arguments and complete characterization of extremal examples on that restricted class. No equation or bound is shown to be equivalent to its inputs by construction, no parameter is fitted and relabeled as a prediction, and the central claims do not collapse to a self-citation chain; the cited preservation facts function as external enabling lemmas rather than load-bearing premises that themselves reduce to the present results.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claims rest on the preservation of multiplicity under the reduction operation and the known invariance under deletion of P3 paths; no free parameters or invented entities appear.

axioms (1)
  • domain assumption Deleting a pendant path P3 from a graph does not change m_L(G)(1)
    Explicitly stated as known in the abstract.

pith-pipeline@v0.9.1-grok · 5803 in / 1210 out tokens · 36399 ms · 2026-06-27T09:40:33.821337+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

15 extracted references · 1 canonical work pages

  1. [1]

    Akbari, E.R

    S. Akbari, E.R. van Dam, M.H. Fakharan, Trees with a large Laplacia n eigenvalue multiplicity, Linear Algebra Appl. 586 (2020) 262–273

    2020

  2. [2]

    Andrade, D.M

    E. Andrade, D.M. Cardoso, G. Past´ en, O. Rojo, On the Faria’s in equality for the Laplacian and signless Laplacian spectra: a unified approach, Linear Algebra Appl. 472 (2015) 81–96. 11

    2015

  3. [3]

    Barik, A.K

    S. Barik, A.K. Lal, S. Pati, On trees with Laplacian eigenvalue one, L inear Multilinear Algebra 56 (6) (2008) 597–610

    2008

  4. [4]

    Du, The multiplicity of eigenvalues of Aα of trees, Ann

    Z. Du, The multiplicity of eigenvalues of Aα of trees, Ann. Comb. (2025), https://doi.org/10.1007/s00026-025-00796-5

    work page doi:10.1007/s00026-025-00796-5 2025

  5. [5]

    Faria, Permanental roots and the star degree of a graph, L inear Algebra Appl

    I. Faria, Permanental roots and the star degree of a graph, L inear Algebra Appl. 64 (1985) 255–265

    1985

  6. [6]

    J.-M. Guo, L. Feng, J. Zhang, On the multiplicity of Laplacian eigenv alues of graphs, Czechoslov. Math. J. 60 (135) (2010) 689–698

    2010

  7. [7]

    Gutman, I

    I. Gutman, I. Sciriha, On the nullity of line graphs of trees, Discre te Math. 232 (2001) 35–45

    2001

  8. [8]

    Grone, R

    R. Grone, R. Merris, V.S. Sunder, The Laplacian spectrum of a gr aph, SIAM J. Matrix Anal. Appl. 11 (1990) 218–238

    1990

  9. [9]

    F. Tian, J. Wang, W. Song, Upper bound of the multiplicity of Laplac ian eigenvalue 1 of trees, Linear Algebra Appl. 724 (2025) 108–119

    2025

  10. [10]

    F. Tian, D. Wong, On the multiplicity of 1 as a Laplacian eigenvalue of a graph, Discrete Math. 349 (2026) 115030

    2026

  11. [11]

    Z. Wang, Q. Chen, J. Guo, X. Li. A relation between multiplicity of 1 as a Laplacian eigenvalue and induced matching numbers in trees. Discrete Math. 348(5) (20 25) 114401

  12. [12]

    X. Wang, Q. Zhou, D. Wong, C. Zhang, F. Tian, The multiplicity of la placian eigenvalue two in a connected graph with a perfect matching. Linear Algebra Appl. 60 9 (2021) 152-162

    2021

  13. [13]

    F. Wen, Q. Huang, On the multiplicity of Laplacian eigenvalues for u nicyclic graphs. Czech. Math. J. 72 (147) (2022) 371-390

    2022

  14. [14]

    D. Wong, W. Zhen, S. Xu, Characterization of trees with Laplac ian eigenvalue multiplicity one less than the number of pendant vertices. Discrete Math. 349 (20 26) 114799

  15. [15]

    J. Yang, L. Wang, Line graphs of trees with the largest eigenva lue multiplicity, Linear Algebra Appl. 676 (2023) 56–65. 12

    2023