pith. sign in

arxiv: 2604.24241 · v1 · submitted 2026-04-27 · 🧮 math.CO

Perfect matchings and A_(α)-spectral radius in 1-binding graphs

Sizhong Zhou , Hongxia Liu This is my paper

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

classification 🧮 math.CO MSC 05C5005C70
keywords perfect matchingA_α-matrixspectral radiusbinding numberTutte's theorem1-binding graphsspectral graph theory
0
0 comments X

The pith

Connected 1-binding graphs of even order have a perfect matching if their A_α-spectral radius is sufficiently large, except for one specific graph.

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

The authors prove that a connected 1-binding graph G of even order n at least n(α) has a perfect matching unless it is the graph formed by joining a vertex to the disjoint union of a large complete graph, a triangle, and an isolated vertex, provided that the A_α-spectral radius of G is at least as large as that of this exceptional graph. This relies on Tutte's theorem that equates perfect matchings to the condition that no set S leaves more odd components than |S|. Readers would care because the spectral radius offers a computable proxy for ensuring the structural property of having a perfect matching in graphs with binding number at least one. The threshold n(α) grows with α to make the inequalities work for smaller α.

Core claim

A connected 1-binding graph G of even order n with n ≥ n(α) has a perfect matching unless G is isomorphic to K_1 ∨ (K_{n-5} ∪ K_3 ∪ K_1) whenever ρ_α(G) ≥ ρ_α(K_1 ∨ (K_{n-5} ∪ K_3 ∪ K_1)), with n(α) = max{18, (2 + 8α)/(1 - 2α)} for α < 1/2 and n(α) = 18 for α = 1/2.

What carries the argument

The A_α-spectral radius ρ_α(G), the largest eigenvalue of the A_α-matrix A_α(G) = αD(G) + (1-α)A(G), which is used to derive bounds that enforce Tutte's condition o(G-S) ≤ |S| in 1-binding graphs.

If this is right

  • The graph satisfies the Tutte condition for having a perfect matching.
  • The only possible exception is the specified join graph K1 ∨ (K_{n-5} ∪ K3 ∪ K1).
  • The result applies uniformly for α in [0, 1/2] with appropriate size thresholds.
  • The spectral condition prevents the existence of a vertex set S that creates too many odd components in G-S.

Where Pith is reading between the lines

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

  • Similar results might hold for the adjacency spectral radius as the case α=0.
  • The exceptional graph could be checked directly to confirm it is 1-binding and lacks a perfect matching.
  • This provides a way to algorithmically certify perfect matchings via eigenvalue computation for this class of graphs.

Load-bearing premise

That any 1-binding graph violating the Tutte condition must have A_α-spectral radius strictly less than the threshold unless it is the exceptional graph.

What would settle it

Construct or identify a connected 1-binding graph with even order exceeding n(α), ρ_α(G) at or above the threshold, but lacking a perfect matching and not isomorphic to the exceptional graph.

read the original abstract

Let $G$ be a graph with vertex set $V(G)$ and edge set $E(G)$. For $\alpha\in[0,1)$, we use $A_{\alpha}(G)$ and $\rho_{\alpha}(G)$ to denote the $A_{\alpha}$-matrix and the $A_{\alpha}$-spectral radius of $G$, respectively. The binding number $\mbox{bind}(G)$ of $G$ is defined by $\mbox{bind}(G)=\min\left\{\frac{|N_G(X)|}{|X|}:\emptyset\neq X\subseteq V(G),N_G(X)\neq V(G)\right\}$. If $\mbox{bind}(G)\geq1$, then $G$ is called 1-binding. A perfect matching in $G$ is a set of nonadjacent edges covering every vertex of $G$. Tutte proved that a graph $G$ of even order has a perfect matching if and only if $o(G-S)\leq|S|$ holds for every $S\subseteq V(G)$ [W. Tutte, The factorization of linear graphs, J. Lond. Math. Soc. 22 (1947) 107--111]. In this paper, we use Tutte's result to prove that a connected 1-binding graph $G$ of even order $n$ with $n\geq n(\alpha)$ has a perfect matching unless $G=K_1\vee(K_{n-5}\cup K_3\cup K_1)$ if $\rho_{\alpha}(G)\geq\rho_{\alpha}(K_1\vee(K_{n-5}\cup K_3\cup K_1))$, where $n(\alpha)$ is defined as follows: $n(\alpha)=\max\{18,\frac{2+8\alpha}{1-2\alpha}\}$ if $\alpha\in[0,\frac{1}{2})$, and $n(\alpha)=18$ if $\alpha=\frac{1}{2}$.

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

1 major / 0 minor

Summary. The paper proves that every connected 1-binding graph G of even order n ≥ n(α) has a perfect matching whenever ρ_α(G) ≥ ρ_α(K_1 ∨ (K_{n-5} ∪ K_3 ∪ K_1)), unless G is exactly the exceptional graph K_1 ∨ (K_{n-5} ∪ K_3 ∪ K_1). The proof invokes Tutte's theorem to reduce the claim to verifying the condition o(G-S) ≤ |S| for all S, using the 1-binding hypothesis to restrict admissible sets S together with case analysis and spectral-radius inequalities that become valid for n large enough (n(α) = max{18, (2+8α)/(1-2α)} when α < 1/2 and 18 when α = 1/2).

Significance. If the corrected statement holds, the result supplies a concrete spectral-radius threshold guaranteeing perfect matchings inside the 1-binding class, thereby linking A_α-spectral theory with binding-number restrictions and Tutte's condition. The approach is standard for spectral extremal problems on matchings and could be useful for further work on binding-number variants of matching theorems.

major comments (1)
  1. [Abstract / main theorem] Abstract (and the main theorem statement): the exceptional graph K_1 ∨ (K_{n-5} ∪ K_3 ∪ K_1) fails to be 1-binding. For even n ≥ 6 let X be the vertex set of the K_3 ∪ K_1 components; then |X| = 4 and N(X) consists of the single joined vertex, so |N(X)|/|X| = 1/4 < 1 and bind(G) ≤ 1/4. Consequently the “unless” clause is vacuous inside the class of 1-binding graphs to which the theorem applies. The statement must be revised to assert that every connected 1-binding G satisfying the order and spectral hypotheses has a perfect matching (the exception lies outside the hypothesis class).

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript and for identifying this important clarification regarding the binding number of the proposed exceptional graph. We agree with the assessment and will revise the statement accordingly.

read point-by-point responses

  1. Referee: [Abstract / main theorem] Abstract (and the main theorem statement): the exceptional graph K_1 ∨ (K_{n-5} ∪ K_3 ∪ K_1) fails to be 1-binding. For even n ≥ 6 let X be the vertex set of the K_3 ∪ K_1 components; then |X| = 4 and N(X) consists of the single joined vertex, so |N(X)|/|X| = 1/4 < 1 and bind(G) ≤ 1/4. Consequently the “unless” clause is vacuous inside the class of 1-binding graphs to which the theorem applies. The statement must be revised to assert that every connected 1-binding G satisfying the order and spectral hypotheses has a perfect matching (the exception lies outside the hypothesis class).

    Authors: We agree with the referee's calculation. Let G = K_1 ∨ (K_{n-5} ∪ K_3 ∪ K_1) with even n ≥ 6. Taking X to be the vertex set of the K_3 ∪ K_1 components gives |X| = 4 and N_G(X) equal to the single vertex of the K_1, so |N_G(X)|/|X| = 1/4 < 1. Thus bind(G) ≤ 1/4 < 1, confirming that G is not 1-binding. Since our theorem is stated only for connected 1-binding graphs, the exceptional graph lies outside the hypothesis class and the “unless” clause is indeed vacuous. We will revise the abstract and the main theorem to remove the exception and assert directly that every connected 1-binding graph G of even order n ≥ n(α) satisfying ρ_α(G) ≥ ρ_α(K_1 ∨ (K_{n-5} ∪ K_3 ∪ K_1)) possesses a perfect matching. The proof itself is unaffected, as the 1-binding hypothesis is used to restrict admissible Tutte sets S throughout the argument. revision: yes

Circularity Check

0 steps flagged

No circularity; external Tutte theorem and explicit inequalities suffice

full rationale

The derivation invokes Tutte's 1947 theorem as an independent external benchmark to equate perfect matchings with the o(G-S) ≤ |S| condition for all S. The 1-binding hypothesis restricts admissible violating sets S, after which the paper performs case analysis to show that any potential violator must have A_α-spectral radius strictly below that of the identified candidate graph when n ≥ n(α). The threshold n(α) is obtained by solving the explicit inequality ρ_α(G) ≥ ρ_α(K1 ∨ (K_{n-5} ∪ K3 ∪ K1)) under the binding-number constraint; this is a direct comparison, not a fitted parameter renamed as a prediction. No step reduces the claimed result to a self-definition, a self-citation chain, or an ansatz smuggled from prior work by the same authors. The exceptional graph's failure to be 1-binding is a statement-level observation but does not create circularity in the proof chain, which remains self-contained against the external Tutte benchmark.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on Tutte's theorem as an external standard result and on the prior definition of the A_alpha matrix; no free parameters are fitted inside the proof and no new entities are postulated.

axioms (1)
  • standard math Tutte's theorem: an even-order graph has a perfect matching if and only if o(G-S) ≤ |S| for every vertex subset S
    Directly invoked to convert the spectral-radius hypothesis into a matching guarantee.

pith-pipeline@v0.9.0 · 5668 in / 1296 out tokens · 67847 ms · 2026-05-08T02:26:58.933355+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

29 extracted references · 29 canonical work pages

  1. [1]

    Woodall, The binding number of a graph and its Anderson number, J

    D. Woodall, The binding number of a graph and its Anderson number, J. Combin. Theory Ser. B 15(3) (1973) 225–255

    work page 1973

  2. [2]

    Nikiforov, Merging theA- andQ-spectral theories, Appl

    V. Nikiforov, Merging theA- andQ-spectral theories, Appl. Anal. Discrete Math. 11 (2017) 81–107

    work page 2017

  3. [3]

    Pirzada, A

    S. Pirzada, A. Rehman, MaximumA α-spectral radius of{C(3,3), C(4,3)}-free graphs, Linear Algebra Appl. 709 (2025) 385–396

    work page 2025

  4. [4]

    Samanta, On bounds ofA α-eigenvalue multiplicity and the rank of a complex unit gain graph, Discrete Math

    A. Samanta, On bounds ofA α-eigenvalue multiplicity and the rank of a complex unit gain graph, Discrete Math. 346 (2023) 113503

    work page 2023

  5. [5]

    M. Bhat, P. Manan, Bounds for the trace norm ofA α matrix of digraphs, Discrete Math. 348 (2025) 114491

    work page 2025

  6. [6]

    X. Lei, S. Li, Spectral extremal results on theA α-spectral radius of graphs withoutK a,b-minor, Appl. Math. Comput. 492 (2025) 129232

    work page 2025

  7. [7]

    S. Zhou, Q. Bian, J. Wu, Sufficient conditions for even factors in graphs, Discrete Appl. Math. 386 (2026) 365–372

    work page 2026

  8. [8]

    S. Zhou, Y. Zhang, T. Zhang, H. Liu, Toughness andA α-spectral radius in graphs, Filomat 40(5) (2026) 1883–1892

    work page 2026

  9. [9]

    Zhou, A result on spanning trees with bounded total excess, Discrete Appl

    S. Zhou, A result on spanning trees with bounded total excess, Discrete Appl. Math. 388 (2026) 130–135

    work page 2026

  10. [10]

    Wu, Characterizing spanning trees via the size or the spectral radius of graphs, Aequationes Math

    J. Wu, Characterizing spanning trees via the size or the spectral radius of graphs, Aequationes Math. 98(6) (2024) 1441–1455

    work page 2024

  11. [11]

    Tutte, The factorization of linear graphs, J

    W. Tutte, The factorization of linear graphs, J. Lond. Math. Soc. 22 (1947) 107–111

    work page 1947

  12. [12]

    O, Spectral radius and matchings in graphs, Linear Algebra Appl

    S. O, Spectral radius and matchings in graphs, Linear Algebra Appl. 614 (2021) 316–324

    work page 2021

  13. [13]

    Zhang, H

    Y. Zhang, H. Lin, Perfect matching and distance spectral radius in graphs and bipartite graphs, Discrete Appl. Math. 304 (2021) 315–322

    work page 2021

  14. [14]

    Y. Zhao, X. Huang, Z. Wang, TheA α-spectral radius and perfect matchings of graphs, Linear Algebra Appl. 631 (2021) 143–155

    work page 2021

  15. [15]

    D. Fan, H. Lin, Binding number,k-factor and spectral radius of graphs, Electron. J. Combin. 31(1) (2024) #P1.30

    work page 2024

  16. [16]

    Y. Hu, Y. Zhang, Binding number, odd [1, b]-factors and the distance spectral radius, Discrete Appl. Math. 360 (2025) 406–413

    work page 2025

  17. [17]

    Wu, Some results on thek-strong parity property in a graph, Comput

    J. Wu, Some results on thek-strong parity property in a graph, Comput. Appl. Math. 45(4) (2026) 138. 10

    work page 2026

  18. [18]

    Wu, Sufficient conditions for a graph with minimum degree to have a component factor, Proc

    J. Wu, Sufficient conditions for a graph with minimum degree to have a component factor, Proc. Rom. Acad. Ser. A Math. Phys. Tech. Sci. Inf. Sci. 27(1) (2026) 3–10

    work page 2026

  19. [19]

    H. Liu, X. Pan, Independence number and minimum degree for path-factor critical uniform graphs, Discrete Appl. Math. 359 (2024) 153–158

    work page 2024

  20. [20]

    Zhou, Some spectral conditions for star-factors in bipartite graphs, Discrete Appl

    S. Zhou, Some spectral conditions for star-factors in bipartite graphs, Discrete Appl. Math. 369 (2025) 124–130

    work page 2025

  21. [21]

    Zhou, Spanning subgraphs and spectral radius in graphs, Aequationes Math

    S. Zhou, Spanning subgraphs and spectral radius in graphs, Aequationes Math. 100(1) (2026) 1

    work page 2026

  22. [22]

    S. Zhou, Q. Bian, Z. Sun, Spectral conditions for path-factors in isolated tough graphs, Discrete Appl. Math. 385 (2026) 228–236

    work page 2026

  23. [23]

    Zhou, Toughness, fractional extendability and distance spectral radius in graphs, J

    S. Zhou, Toughness, fractional extendability and distance spectral radius in graphs, J. Korean Math. Soc. 62(3) (2025) 601–617

    work page 2025

  24. [24]

    J. Wu, S. Zhou, H. Liu, A spectral condition for spanning trees with restricted degrees in bipartite graphs, Proc. Rom. Acad. Ser. A Math. Phys. Tech. Sci. Inf. Sci. 27(1) (2026) 19–24

    work page 2026

  25. [25]

    Zhou, Some spectral conditions for odd [1, b]-factors in tough graphs, Bull

    S. Zhou, Some spectral conditions for odd [1, b]-factors in tough graphs, Bull. Math. Soc. Sci. Math. Roumanie, Accept

    work page

  26. [26]

    Zheng, J

    J. Zheng, J. Wang, X. Huang, Spectral conditions for graphs having all (fractional) [a, b]-factors, Discrete Math. 347 (2024) 113975

    work page 2024

  27. [27]

    J. Wu, J. Wang, L. Kang, Spectral conditions for matching extension, Appl. Math. Comput. 483 (2024) 128982

    work page 2024

  28. [28]

    L. You, M. Yang, W. So, W. Xi, On the spectrum of an equitable quotient matrix and its application, Linear Algebra Appl. 577 (2019) 21–40

    work page 2019

  29. [29]

    Haemers, Interlacing eigenvalues and graphs, Linear Algebra Appl

    W. Haemers, Interlacing eigenvalues and graphs, Linear Algebra Appl. 227-228 (1995) 593–616. 11

    work page 1995