pith. sign in

arxiv: 2605.04438 · v1 · submitted 2026-05-06 · 🧮 math.CO

Extremal problems on [a, b]-covered graphs

Qixuan Yuan , Ruifang Liu , Jinjiang Yuan This is my paper

Pith reviewed 2026-05-08 17:37 UTC · model grok-4.3

classification 🧮 math.CO
keywords [a,b]-covered graphsmatching covered graphsextremal graph problemsspectral radiusgraph factorsminimum degreeH_{n,a}
0
0 comments X

The pith

H_{n,a} uniquely maximizes both edge count and spectral radius among all non-[a,b]-covered graphs.

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

The paper seeks the graphs on n vertices with the most edges and the largest spectral radius that fail to be [a,b]-covered, meaning they contain at least one edge that lies in no [a,b]-factor. Earlier work had settled the same question for the narrower class of graphs that contain no [a,b]-factor at all; the authors extend those results to the broader class of non-covered graphs by proving that the same graph H_{n,a} = K_{a-1} joined to (K_{n-a} union an isolated vertex) remains the unique maximizer for both quantities. They obtain the complete characterizations by combining a new minimum-degree forcing argument with spectral and structural analysis.

Core claim

Non-[a,b]-covered graphs exhibit highly complex structures, yet the extremal graphs that maximize the number of edges or the spectral radius in this class are completely characterized and coincide with the graph H_{n,a} for a ≤ b and b ≥ 2 (and the analogous statement holds for non-matching-covered graphs when a = b = 1).

What carries the argument

The minimum-degree forcing technique, which narrows possible structures of extremal non-covered graphs by examining minimum-degree conditions and combining them with spectral-structural analysis.

If this is right

  • The extremal graph identified for graphs containing no [a,b]-factor remains extremal for the strictly larger family of non-[a,b]-covered graphs.
  • Both the size-maximizing and spectral-radius-maximizing graphs are unique and equal to H_{n,a}.
  • The results strengthen the earlier Hao-Li theorems on [a,b]-factor-free graphs by extending them to the covered-property setting.

Where Pith is reading between the lines

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

  • The fact that the same graph is extremal suggests that the primary obstruction to being covered is already captured by the absence of factors.
  • The minimum-degree forcing method may apply to other extremal problems involving graph properties whose structural descriptions are similarly intricate.
  • It is natural to ask whether H_{n,a} also extremalizes additional invariants (such as the adjacency matrix energy or the number of spanning trees) within the same class.

Load-bearing premise

The minimum-degree forcing technique is sufficient to produce complete characterizations despite the complex structures of non-[a,b]-covered graphs.

What would settle it

Any non-[a,b]-covered graph on n vertices with more than binom(n-1,2) + a - 1 edges or with spectral radius strictly larger than that of H_{n,a}.

read the original abstract

A graph $G$ is $[a,b]$-covered if for each edge $e$ of $G$ there is an $[a,b]$-factor containing it. For $a=b=1$, an $[a,b]$-covered graph is a matching covered graph. The structural theory of matching covered graphs constitutes a cornerstone of modern matching theory. Determining whether a given graph is matching covered is a fundamental problem in structural graph theory. Lucchesi et al. [SIAM J. Discrete Math., 2018] showed that a connected graph $G$ is matching covered if and only if every barrier of $G$ is a stable set. In this paper, we completely characterize the extremal graphs that maximize the size or the spectral radius among all non-matching-covered graphs. For $a \leq b$ and $b \geq 2,$ Hao and Li [Electron. J. Combin., 2024] investigated the extremal problems on $[a,b]$-factor graphs: If $G$ contains no $[a,b]$-factors, then $e(G)\leq \binom{n-1}{2}+a-1$ with equality if and only if $G\cong H_{n,a},$ where $H_{n,a} = K_{a-1} \vee (K_{n-a} \cup K_1).$ Moreover, if $G$ contains no $[a,b]$-factors, then $\rho(G)\leq \rho(H_{n,a})$ with equality if and only if $G \cong H_{n,a}.$ Judging from the structral characterization, non-$[a,b]$-covered graphs exhibit highly complex structures, making the associated extremal problems significantly challenging. To overcome this, we develop a novel minimum-degree forcing technique. Combining this technique and spectral-structural analysis, we in this paper provide complete characterizations of the extremal graphs that maximize the size or the spectral radius within the set of non-$[a,b]$-covered graphs. An intriguing phenomenon revealed by our results is that $H_{n,a}$ remains both the size-extremal graph and the spectral extremal graph for this larger set of non-$[a,b]$-covered graphs. Consequently, our results strengthen the results of Hao-Li.

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

Summary. The paper claims to completely characterize the n-vertex graphs that maximize the number of edges and the spectral radius among all non-[a,b]-covered graphs. For the matching-covered case a=b=1 it uses barrier properties; for a≤b with b≥2 it introduces a minimum-degree forcing technique combined with spectral-structural analysis to show that H_{n,a} = K_{a-1} ∨ (K_{n-a} ∪ K_1) is the unique maximizer for both quantities, thereby strengthening the earlier Hao-Li bounds that applied only to graphs containing no [a,b]-factor at all.

Significance. If the characterizations are correct, the work is a meaningful extension of extremal results in matching and factor theory to the strictly larger class of non-covered graphs. The observation that the same extremal graph H_{n,a} remains unique for both the edge-maximization and spectral-radius problems is noteworthy, and the newly introduced minimum-degree forcing technique is a potentially reusable tool for other structural questions involving factors and coverings.

minor comments (3)
  1. [§2] §2 (Preliminaries): the notation for an [a,b]-factor and for an edge being covered by such a factor should be stated explicitly with a short example for a=2, b=3 to avoid ambiguity when the reader reaches the forcing arguments.
  2. [Theorem 1.3] Theorem 1.3 and its proof: the reduction from the general a≤b case to the a=b=1 case is only sketched; a short paragraph clarifying how the barrier condition lifts to the general setting would improve readability.
  3. [Figure 1] Figure 1: the drawing of H_{n,a} for n=7, a=3 is too small to read the partition labels; enlarging it or adding a caption that explicitly identifies the clique sizes would help.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and positive assessment of our manuscript. We appreciate the recognition that our results meaningfully extend extremal problems from graphs without [a,b]-factors to the larger class of non-[a,b]-covered graphs, and that the uniqueness of H_{n,a} for both the edge-maximization and spectral-radius problems is noteworthy. The referee's summary accurately describes our approach, including the barrier properties for a=b=1 and the minimum-degree forcing technique combined with spectral-structural analysis for b≥2. As the recommendation is minor revision but the major comments section contains no specific points, we provide no point-by-point rebuttals below.

Circularity Check

0 steps flagged

No significant circularity; derivation relies on independent prior characterizations plus new technique

full rationale

The paper's central results extend Hao-Li extremal bounds on non-[a,b]-factor graphs to the strictly larger class of non-[a,b]-covered graphs by introducing a minimum-degree forcing technique combined with spectral-structural analysis. This rests on the independent structural theorem of Lucchesi et al. (every barrier is stable iff matching-covered) and the Hao-Li size/spectral bounds for the factor case; neither is a self-citation, nor is any claimed extremal graph H_{n,a} obtained by fitting parameters or by renaming a prior result. The derivation chain therefore remains self-contained against external benchmarks and does not reduce any prediction to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard graph-theoretic definitions and previously published structural results; no free parameters, new entities, or ad-hoc axioms are introduced.

axioms (2)
  • standard math Finite undirected simple graphs and the standard definitions of factors, barriers, and spectral radius.
    Foundational assumptions shared by all papers in the area.
  • domain assumption The barrier characterization of matching covered graphs due to Lucchesi et al. holds.
    Explicitly invoked as the structural foundation for the a=b=1 case.

pith-pipeline@v0.9.0 · 5735 in / 1298 out tokens · 60500 ms · 2026-05-08T17:37:55.390568+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]

    Cioab ˘a, D.N

    S. Cioab ˘a, D.N. Desai, M. Tait, The spectral radius of graphs with no odd wheels, European J. Combin.99(2022) 103420

    work page 2022

  2. [2]

    Cioab ˘a, L.H

    S. Cioab ˘a, L.H. Feng, M. Tait, X.-D. Zhang, The maximum spectral radius of graphs without friendship subgraphs,Electron. J. Combin.27(2020) P4.22

    work page 2020

  3. [3]

    de Carvalho, C.H.C

    M.H. de Carvalho, C.H.C. Little, Matching covered graphs with three removable classes,Electron. J. Combin.21(2014) P2.13

    work page 2014

  4. [4]

    de Carvalho, C.L

    M.H. de Carvalho, C.L. Lucchesi, Matching covered graphs and subdivisions ofK 4 and C6,J. Combin. Theory Ser . B66(1996) 263-268

    work page 1996

  5. [5]

    de Carvalho, C.L

    M.H. de Carvalho, C.L. Lucchesi, U.S.R. Murty, On a conjecture of Lov ´asz concerning bricks. I. The characteristic of a matching covered graph,J. Combin. Theory Ser . B85(2002) 94-136

    work page 2002

  6. [6]

    Erd ˝os, Z

    P. Erd ˝os, Z. F ¨uredi, R.J. Gould, D.S. Gunderson, Extremal graphs for intersecting triangles,J. Combin. Theory Ser . B64(1995) 89-100

    work page 1995

  7. [7]

    Guiduli, Spectral Extrema for Graphs, Ph.D

    B.D. Guiduli, Spectral Extrema for Graphs, Ph.D. Thesis, Department of Mathematics, University of Chicago, 1996

    work page 1996

  8. [8]

    Hao, S.C

    Y .F. Hao, S.C. Li, Tur ´an-type problems on [a,b]-factors of graphs, and beyond, Electron. J. Combin.31(2024) P3.23

    work page 2024

  9. [9]

    J.H. He, E.L. Wei, D. Ye, S.H. Zhai, On perfect matchings in matching covered graphs,J. Graph Theory90(2019) 535-546

    work page 2019

  10. [10]

    Hong, J.L

    Y . Hong, J.L. Shu, K.F. Fang, A sharp upper bound of the spectral radius of graphs, J. Combin. Theory Ser . B81(2001) 177-183. 16

    work page 2001

  11. [11]

    Kothari, U.S.R

    N. Kothari, U.S.R. Murty,K 4-free and C6-free planar matching covered graphs,J. Graph Theory82(2016) 5-32

    work page 2016

  12. [12]

    Little, A theorem on connected graphs in which every edge belongs to a 1-factor,J

    C.H.C. Little, A theorem on connected graphs in which every edge belongs to a 1-factor,J. Austral. Math. Soc.18(1974) 450-452

    work page 1974

  13. [13]

    Liu, On (g,f)-covered graphs,Acta Math

    G.Z. Liu, On (g,f)-covered graphs,Acta Math. Sci.8(1988) 181-184

    work page 1988

  14. [14]

    L.L. Liu, B. Ning, Spectral Tur ´an-type problems on sparse spanning graphs, Discrete Math.349(2026) 115016

    work page 2026

  15. [15]

    Q.H. Liu, Q. Cui, X. Feng, F.L. Lu, A characterization of nonfeasible sets in matching covered graphs,J. Graph Theory95(2020) 509-526

    work page 2020

  16. [16]

    Lov ´asz, Subgraphs with prescribed valencies,J

    L. Lov ´asz, Subgraphs with prescribed valencies,J. Combinatorial Theory8(1970) 391-416

    work page 1970

  17. [17]

    Lucchesi, M.H

    C.L. Lucchesi, M.H. de Carvalho, N. Kothari, U.S.R. Murty, On two unsolved problems concerning matching covered graphs,SIAM J. Discrete Math.32(2018) 1478-1504

    work page 2018

  18. [18]

    Mantel, Problem 28, solution by H

    W. Mantel, Problem 28, solution by H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh and W.A. Wythoff,Wiskundige Opgaven10(1907) 60-61

    work page 1907

  19. [19]

    Nikiforov, Some inequalities for the largest eigenvalue of a graph,Combin

    V . Nikiforov, Some inequalities for the largest eigenvalue of a graph,Combin. Probab. Comput.11(2002) 179-189

    work page 2002

  20. [20]

    Nikiforov, Bounds on graph eigenvalues

    V . Nikiforov, Bounds on graph eigenvalues. II,Linear Algebra Appl.427(2007) 183-189

    work page 2007

  21. [21]

    Nikiforov, The spectral radius of graphs without paths and cycles of specified length,Linear Algebra Appl.432(2010) 2243-2256

    V . Nikiforov, The spectral radius of graphs without paths and cycles of specified length,Linear Algebra Appl.432(2010) 2243-2256

    work page 2010

  22. [22]

    Szigeti, On generalizations of matching-covered graphs,European J

    Z. Szigeti, On generalizations of matching-covered graphs,European J. Combin.22 (2001) 865-877

    work page 2001

  23. [23]

    Tur ´an, On an extremal problem in graph theory,Mat

    P. Tur ´an, On an extremal problem in graph theory,Mat. Fiz. Lapok48(1941) 436- 452

    work page 1941

  24. [24]

    Tutte, The factors of graphs,Canad

    W.T. Tutte, The factors of graphs,Canad. J. Math.4(1952) 314-328

    work page 1952

  25. [25]

    Wang, L.Y

    J. Wang, L.Y . Kang, Y .S. Xue, On a conjecture of spectral extremal problems,J. Combin. Theory Ser . B159(2023) 20-41

    work page 2023

  26. [26]

    Wang, Z.Y

    J. Wang, Z.Y . Ni, L.Y . Kang, Y .-Z. Fan, Spectral extremal graphs for edge blow-up of star forests,Discrete Math.347(2024) 114141

    work page 2024

  27. [27]

    Wei, S.G

    J. Wei, S.G. Zhang, Proof of a conjecture on the spectral radius condition for [a,b]- factors,Discrete Math.346(2023) 113269

    work page 2023

  28. [28]

    Wilf, Spectral bounds for the clique and independence numbers of graphs,J

    H.S. Wilf, Spectral bounds for the clique and independence numbers of graphs,J. Combin. Theory Ser . B40(1986) 113-117

    work page 1986

  29. [29]

    Zhai, R.F

    M.Q. Zhai, R.F. Liu, J. Xue, A unique characterization of spectral extrema for friendship graphs,Electron. J. Combin.29(2022) P3.32

    work page 2022