pith. sign in

arxiv: 2604.16151 · v1 · submitted 2026-04-17 · 🧮 math.CO

Extremal results for graphs with binding number strictly less than 1/r

Ruifang Liu , Hongyu Chen , Ao Fan This is my paper

Pith reviewed 2026-05-10 07:59 UTC · model grok-4.3

classification 🧮 math.CO
keywords binding numberextremal graphspectral radiusedge extremalbipartite graphsWoodall's parametergraph connectivity
0
0 comments X

The pith

Graphs with binding number strictly below 1/r have a unique maximum-size and maximum-spectral-radius example for each order n and integer r.

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

The paper shows that the binding number condition b(G) < 1/r severely limits how many edges a graph can have. It identifies exactly one graph on n vertices that achieves the largest possible number of edges and the largest spectral radius under this restriction. A reader cares because the binding number measures a form of expansion or connectivity, so knowing the densest graphs just below each threshold 1/r reveals the sharp boundary between more and less connected graph families. The result holds for both general graphs and the subclass of bipartite graphs.

Core claim

For every integer r at least 1 and every n, there is a unique graph on n vertices with binding number less than 1/r that has more edges than any other such graph and a larger spectral radius than any other such graph.

What carries the argument

The binding number b(G), defined as the minimum of |N(S)|/|S| over nonempty proper subsets S, together with the structural characterization that isolates the unique maximizer under the strict inequality b(G) < 1/r.

If this is right

  • The maximum number of edges among n-vertex graphs with b(G) < 1/r equals the edge count of this unique extremal graph.
  • The spectral radius of any n-vertex graph with b(G) < 1/r is bounded above by the spectral radius of the same extremal graph.
  • When the graphs are further restricted to be bipartite, the same unique graph remains the maximizer for both edge count and spectral radius.
  • Any graph with b(G) at least 1/r necessarily exceeds the edge count of the extremal graph for the strict inequality.

Where Pith is reading between the lines

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

  • The characterization may supply explicit new inequalities relating binding number to toughness for the identified family of graphs.
  • The extremal construction is likely a specific unbalanced complete bipartite graph whose parts can be used to verify the binding-number bound by direct calculation.
  • The same style of argument could extend to other monotone graph parameters that are comparable to binding number.
  • Knowing the exact maximizers would allow systematic construction of graphs that achieve prescribed values of binding number just below each threshold 1/r.

Load-bearing premise

The binding number condition b(G) < 1/r can be used to derive a complete structural characterization of a unique extremal graph without additional hidden constraints on n or the graph class.

What would settle it

Finding a graph on n vertices with b(G) < 1/r that contains strictly more edges than the claimed unique extremal graph would disprove the characterization.

Figures

Figures reproduced from arXiv: 2604.16151 by Ao Fan, Hongyu Chen, Ruifang Liu.

Figure 1
Figure 1. Figure 1: Graph D(p1, p2, . . . , ph; q1, q2, . . . , qh) [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
read the original abstract

The binding number $b(G)$ of a graph, introduced by Woodall [J. Combin. Theory, Ser. B, 1973], is a central topic of both structural and extremal graph theory. It is closely related to fundamental combinatorial and structural properties of graphs. The graphs with $b(G)\geq1$ exhibit strong expansion properties and a highly connected global structure. In contrast, the structure for graphs with $b(G)<1$ remains far less well understood. Kane et al. [J. Graph Theory, 1981] proved that if $b(G)<1$, then every binding set of $G$ is independent. Goddard and Swart [Quaest. Math., 1990] showed that if $b(G)\leq1$, then the toughness $\tau(G)\leq b(G).$ This makes it particularly interesting to investigate extremal problems for graphs with \(b(G)<1\). For any integer $r\geq1,$ we completely characterize the unique extremal graph that maximizes the size (spectral radius) among all graphs of order $n$ satisfying $b(G)<\frac{1}{r}.$ For any bipartite graph $G=(X,Y)$ on $n$ vertices, it is readily seen that $b(G)\leq\min\{|X|/|Y|,|Y|/|X|\}\leq1.$ Notably, the complete balanced bipartite graph $K_{\frac{n}{2}, \frac{n}{2}}$ achieves the maximum size (spectral radius) among all bipartite graphs with $b(G)=1$. In this paper, we completely determine the extremal graphs maximizing the size or the spectral radius among all bipartite graphs with $b(G)<\frac{1}{r}$, where $r\geq1$ is an integer.

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 / 1 minor

Summary. The manuscript claims to completely characterize the unique extremal n-vertex graph that maximizes the number of edges (and, separately, the spectral radius) among all graphs G with binding number b(G) < 1/r for any fixed integer r ≥ 1. A parallel result is given for bipartite graphs satisfying the same binding-number bound.

Significance. If the claimed characterizations hold, the work would supply a precise structural description of the largest graphs (edge-maximal or spectral-radius-maximal) that necessarily possess a set S with |N(S)|/|S| < 1/r. This extends earlier results on graphs with b(G) < 1 or b(G) ≤ 1 and connects binding number, toughness, and extremal problems in a concrete way. The uniqueness statements, if verified, would be particularly useful for subsequent spectral or structural applications.

major comments (1)
  1. Abstract and main theorem statements: the claimed complete, unique characterization for every n does not explicitly distinguish the regime n > r + 1 from n ≤ r + 1. When n > r + 1 one has b(K_n) = 1/(n-1) < 1/r, so K_n itself lies in the feasible class and is trivially the unique maximizer of both edge count and spectral radius. When n ≤ r + 1, K_n is excluded and the extremal graph must be a proper subgraph; the structural description necessarily changes. Without an explicit case split on the relation between n and r, the universality asserted in the central claim is not yet established.
minor comments (1)
  1. Abstract: the parenthetical phrasing 'maximizes the size (spectral radius)' is ambiguous. It would be clearer to state that the paper solves the two extremal problems (edge count and spectral radius) separately.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for identifying the need for an explicit case distinction in the statements of our main results. We address this point below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: Abstract and main theorem statements: the claimed complete, unique characterization for every n does not explicitly distinguish the regime n > r + 1 from n ≤ r + 1. When n > r + 1 one has b(K_n) = 1/(n-1) < 1/r, so K_n itself lies in the feasible class and is trivially the unique maximizer of both edge count and spectral radius. When n ≤ r + 1, K_n is excluded and the extremal graph must be a proper subgraph; the structural description necessarily changes. Without an explicit case split on the relation between n and r, the universality asserted in the central claim is not yet established.

    Authors: We agree that the current formulation of the abstract and the main theorem statements would be clearer with an explicit case split on the relationship between n and r. Our characterization already identifies K_n as the unique maximizer when n > r + 1 (since b(K_n) = 1/(n-1) < 1/r) and a different extremal graph when n ≤ r + 1 (where K_n is excluded because b(K_n) ≥ 1/r). We will revise the abstract and the statements of the principal theorems to separate these two regimes explicitly, thereby confirming that the claimed uniqueness holds for every n. revision: yes

Circularity Check

0 steps flagged

No circularity; characterization derives from binding number definition and standard extremal methods

full rationale

The paper states a complete structural characterization of the unique extremal graph maximizing edges or spectral radius under the constraint b(G) < 1/r for integer r >= 1. This rests on the explicit definition of binding number b(G) (introduced by Woodall and analyzed in independent prior works by Kane et al. and Goddard-Swart) together with classical extremal graph techniques. No self-definitional loops appear, no parameters are fitted to data and then relabeled as predictions, and no load-bearing self-citations or uniqueness theorems imported from the authors' prior work are invoked. The derivation chain therefore remains independent of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on the established definition of binding number from Woodall (1973) and standard facts about spectral radius and bipartite graphs; no new free parameters or invented entities are introduced in the abstract.

axioms (2)
  • domain assumption Binding number b(G) is defined as the minimum of |N(S)|/|S| over non-empty proper subsets S with N(S) ≠ V(G).
    Central definition invoked throughout the claimed characterization.
  • domain assumption Standard results on toughness and independent sets for graphs with b(G)<1 from Kane et al. and Goddard-Swart.
    Used to motivate the extremal problem.

pith-pipeline@v0.9.0 · 5636 in / 1205 out tokens · 31484 ms · 2026-05-10T07:59:24.478475+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

21 extracted references · 21 canonical work pages

  1. [1]

    Bhattacharya, S

    A. Bhattacharya, S. Friedland, U.N. Peled, On the first eigenvalue of bipartite graphs,Electron. J. Combin.15(2008) R144

    work page 2008

  2. [2]

    Brouwer, W.H

    A.E. Brouwer, W.H. Haemers, Spectra of graphs, Springer, Berlin, 2011

    work page 2011

  3. [3]

    Bauer, E

    D. Bauer, E. Schmeichel, Binding number, minimum degree, and cycle structure in graphs,J. Graph Theory71(2012) 219-228

    work page 2012

  4. [4]

    Bauer, M

    D. Bauer, M. Yatauro, N. Kahl, E. Schmeichel, Best monotone degree conditions for binding number,Discrete Math.311(2011) 2037-2043

    work page 2011

  5. [5]

    Bondy, U.S.R

    J.A. Bondy, U.S.R. Murty, Graph Theory, Grad. Texts in Math. vol. 244, Springer, New York, 2008

    work page 2008

  6. [6]

    Chen, Binding number and toughness for matching extension,Discrete Math

    C.P. Chen, Binding number and toughness for matching extension,Discrete Math. 146(1995) 303-306

    work page 1995

  7. [7]

    Chv´atal, Tough graphs and Hamiltonian circuits,Discrete Math.5(1973) 215- 228

    V . Chv´atal, Tough graphs and Hamiltonian circuits,Discrete Math.5(1973) 215- 228

    work page 1973

  8. [8]

    Fan, H.Q

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

    work page 2024

  9. [9]

    Godsil, G.F

    C. Godsil, G.F. Royle, Algebraic graph theory, Springer-Verlag, New York, 2001

    work page 2001

  10. [10]

    Goddard, H.C

    W.D. Goddard, H.C. Swart, On the toughness of a graph,Quaest. Math.13(1990) 217-232. 22

    work page 1990

  11. [11]

    Haemers, Interlacing eigenvalues and graphs,Linear Algebra Appl.226-228 (1995) 593-616

    W.H. Haemers, Interlacing eigenvalues and graphs,Linear Algebra Appl.226-228 (1995) 593-616

    work page 1995

  12. [12]

    Hao, S.C

    Y .F. Hao, S.C. Li, Y .T. Yu, Bipartite binding number,k-factor and spectral radius of bipartite graphs,Discrete Math.348(2025) 114511

    work page 2025

  13. [13]

    Z.Q. Hu, K.H. Law, W. Zang, An optimal binding number condition for bipancyclism,SIAM J. Discrete Math.27(2013) 1117-1126

    work page 2013

  14. [14]

    M. Kano, N. Tokushige, Binding numbers andf-factors of graphs,J. Combin. Theory Ser . B54(1992) 213-221

    work page 1992

  15. [15]

    Katerinis, D.R

    P. Katerinis, D.R. Woodall, Binding number of graphs and the existence ofk-factors, Quart. J. Math. Oxford Ser .38(1987) 221-228

    work page 1987

  16. [16]

    Kane, S.P

    V .G. Kane, S.P. Mohanty, E.G. Straus, Which rational numbers are binding numbers, J. Graph Theory5(1981) 379-384

    work page 1981

  17. [17]

    J. Lyle, W. Goddard, The binding number of a graph and its cliques,Discrete Appl. Math.157(2009) 3336-3340

    work page 2009

  18. [18]

    Qian, Two sufficient conditions for the existence ofk-factors in bipartite graphs, Shandong Daxue Xuebao Ziran Kexue Ban36(2001) 477-480

    J.B. Qian, Two sufficient conditions for the existence ofk-factors in bipartite graphs, Shandong Daxue Xuebao Ziran Kexue Ban36(2001) 477-480

    work page 2001

  19. [19]

    Robertshaw, D.R

    A.M. Robertshaw, D.R. Woodall, Binding number conditions for matching extension,Discrete Math.248(2002) 169-179

    work page 2002

  20. [20]

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

    D.R. Woodall, The binding number of a graph and its Anderson number,J. Combin. Theory, Ser . B15(1973) 225-255

    work page 1973

  21. [21]

    Woodall, A sufficient condition for Hamiltonian circuits,J

    D.R. Woodall, A sufficient condition for Hamiltonian circuits,J. Combin. Theory, Ser . B25(1978) 184-186

    work page 1978