pith. sign in

arxiv: 2605.21998 · v1 · pith:TUONWYIOnew · submitted 2026-05-21 · 🧮 math.SP

Minimally (k,k)-edge-connected graphs via spectral radius

Yu Wang , Dan Li , Huiqiu Lin This is my paper

Pith reviewed 2026-05-22 02:25 UTC · model grok-4.3

classification 🧮 math.SP
keywords spectral radiusminimally edge-connected graphsedge-connectivityextremal graph problemsedge switchingeigenvector methodsgraph theory
0
0 comments X

The pith

The graphs maximizing spectral radius among minimally (k,k)-edge-connected graphs are characterized for fixed order and fixed size.

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

This paper solves two extremal problems for the largest spectral radius inside the family of minimally (k,k)-edge-connected graphs. One problem fixes the number of vertices and asks which graph in the family has the biggest spectral radius; the other fixes the number of edges instead. The authors use an existing structural description of all such graphs, then apply edge-switching operations and comparisons of pairs of eigenvectors to decide which members of the family are extremal. The results hold for every k and recover the earlier solutions known only for k equals 2.

Core claim

For l greater than 1, the l-edge-connectivity of a graph G is the smallest number of edges whose deletion creates at least l components. A graph is minimally (k,l)-edge-connected when this number is at least k, yet drops below k after the removal of any single edge. We resolve the fixed-order and fixed-size versions of the Brualdi-Solheid and Brualdi-Hoffman problems in the special case l equals k: the minimally (k,k)-edge-connected graphs of given order or size that attain the maximum spectral radius are characterized by combining the structural framework of Hennayake, Lai, Li, and Mao with edge-switching and double-eigenvector arguments.

What carries the argument

Edge-switching operations together with double-eigenvector comparisons, applied on top of the structural classification of minimally (k,k)-edge-connected graphs.

If this is right

  • Sharp upper bounds on the spectral radius hold for the entire family of minimally (k,k)-edge-connected graphs on n vertices.
  • The same sharp bounds hold when the number of edges rather than vertices is prescribed.
  • The extremal graphs are identified explicitly for every positive integer k.
  • The k equals 2 cases proved earlier are recovered as special instances of the general result.

Where Pith is reading between the lines

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

  • The same switching-plus-eigenvector technique may extend to the case where the two connectivity parameters differ, that is, to minimally (k,l)-edge-connected graphs with k not equal to l.
  • It would be possible to test whether the same extremal graphs remain maximal when further restrictions such as planarity or bounded degree are added.
  • Numerical checks for small k and modest n can verify that the ordering of spectral radii among the candidate graphs matches the analytic prediction.

Load-bearing premise

The structural results of Hennayake, Lai, Li, and Mao continue to classify the possible edge configurations of minimally (k,k)-edge-connected graphs for arbitrary k.

What would settle it

A direct computation of spectral radii for all minimally (3,3)-edge-connected graphs on twelve vertices, checking whether any graph outside the predicted family exceeds the claimed maximum radius.

Figures

Figures reproduced from arXiv: 2605.21998 by Dan Li, Huiqiu Lin, Yu Wang.

Figure 1
Figure 1. Figure 1: The vertex labels of K1(t1, t2, t3) and K1(t1, t2 + t3 + 2, 0). Proposition 3.1. ρ(K1(t1, t2, t3)) < ρ(K1(t1, t2 + t3 + 2, 0)), where 2t1 + t2 + t3 + k + 2 = n. Proof. Suppose that E1 = {vw′ i | 1 ≤ i ≤ 2} + {u ∗wi | 1 ≤ i ≤ t3} + {vwi | 1 ≤ i ≤ t3} and E2 = {w ′ iwj | 1 ≤ i ≤ 2, 1 ≤ j ≤ t3}. Let G1 = K1(t1, t2, t3) and let G′ 1 = G1 − E2 + E1, where the labels of V (G) and V (G′ ) are illustrated in [PIT… view at source ↗
Figure 2
Figure 2. Figure 2: The vertex labels of K(t1, t2) and K(0, 2t1 + t2). Proposition 3.2. ρ(K(t1, t2)) < ρ(K(0, 2t1 + t2)), where 2t1 + t2 + k = n and t2 ̸= 0. Proof. Assume that E1 = {vui | 1 ≤ i ≤ 2t1} and E2 = {uiui+1 | 1 ≤ i ≤ 2t1 − 1 and i is an odd integer}. Let G2 = K(t1, t2) and G′ 2 = G2 − E2 + E1. Clearly, ρ(G′ 2 ) ∼= ρ(K(0, 2t1 + t2)). Their vertices be labeled as in [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The structure of G∗ , where t1 ≥ 0, p + Pq i=1 = |R| and Pp i=1 ri + 2q = |A1|. Note that dA1 (wi) ≥ 2 for all wi ∈ R. From Claims 8-10, we deduce that G∗ has the structure shown in [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
read the original abstract

For $l > 1$, the $l$-edge-connectivity $\kappa'_l(G)$ of a connected graph $G$ is defined as the minimum number of edges whose removal leaves a graph with at least $l$ components. A graph is minimally $(k,l)$-edge-connected if $\kappa'_l(G)\geq k$ but for any edge $e\in E(G)$ satisfies that $\kappa'_l(G-e)< k$. Motivated by two foundational extremal problems: Brualdi and Solheid's problem [SIAM J. Algebra Discrete Methods (1986)] for graphs of fixed order: determine sharp upper bounds for the spectral radius over graph families and characterize extremal graphs; and its fixed size analogue proposed by Brualdi and Hoffman [Linear Algebra Appl. (1985)], we resolve both problems for minimally $(k,k)$-edge-connected graphs. Building on the structural framework of Hennayake, Lai, Li, and Mao [J. Graph Theory (2003)], we combine edge-switching method and double eigenvectors skill to characterize the graphs maximizing the spectral radius among all minimally $(k,k)$-edge-connected graphs of prescribed order or size. Our results generalize the $k=2$ cases established by Lou, Min, and Huang [Electron. J. Comb. (2023)] and Chen and Guo [Discrete Math. (2019)].

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

Summary. The paper resolves the Brualdi-Solheid problem (maximum spectral radius for fixed order n) and the Brualdi-Hoffman problem (fixed size m) for the family of minimally (k,k)-edge-connected graphs. It characterizes the extremal graphs by combining the edge-switching method with double-eigenvector comparisons, building directly on the structural classification of such graphs given by Hennayake, Lai, Li, and Mao (J. Graph Theory, 2003). The results are stated to generalize the k=2 cases previously obtained by Lou-Min-Huang and Chen-Guo.

Significance. If the claims are correct, the work supplies the first complete extremal characterization for spectral radius in this connectivity family for general k, thereby extending the scope of Brualdi-type problems to minimally (k,k)-edge-connected graphs. The methodological combination of switching and double eigenvectors is a reusable technique whose correctness would strengthen the literature on spectral extremal problems under edge-connectivity constraints.

major comments (1)
  1. [§2 (structural framework) and proofs of Theorems 1.1–1.2] The central characterization (Theorems 1.1 and 1.2, and their proofs) invokes the structural framework of Hennayake-Lai-Li-Mao (2003) to enumerate all possible edge configurations of minimally (k,k)-edge-connected graphs. The manuscript does not contain an explicit verification or case analysis showing that this 2003 classification remains exhaustive for arbitrary k ≥ 3; any additional configurations arising for larger k would invalidate the completeness of the subsequent edge-switching comparisons and the double-eigenvector inequalities.
minor comments (2)
  1. [Abstract and §1] The phrase 'double eigenvectors skill' in the abstract and introduction should be replaced by the standard term 'double-eigenvector technique' for precision and readability.
  2. [Proof sections] When lemmas from Hennayake et al. (2003) are applied, the precise statement (lemma number and page) should be cited at each use rather than a general reference to the paper.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the detailed and constructive report. The single major comment raises an important point about the completeness of the structural framework for general k. We address it below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [§2 (structural framework) and proofs of Theorems 1.1–1.2] The central characterization (Theorems 1.1 and 1.2, and their proofs) invokes the structural framework of Hennayake-Lai-Li-Mao (2003) to enumerate all possible edge configurations of minimally (k,k)-edge-connected graphs. The manuscript does not contain an explicit verification or case analysis showing that this 2003 classification remains exhaustive for arbitrary k ≥ 3; any additional configurations arising for larger k would invalidate the completeness of the subsequent edge-switching comparisons and the double-eigenvector inequalities.

    Authors: We agree that an explicit verification would improve clarity. The classification theorem in Hennayake, Lai, Li, and Mao (J. Graph Theory, 2003) is stated and proved for general k without restrictions that would exclude k ≥ 3; their argument relies only on the definition of minimal (k,k)-edge-connectivity and proceeds by considering the possible ways to achieve exactly k edge-disjoint paths between any pair of vertices while ensuring minimality. Nevertheless, to directly address the referee's concern, we will insert a short subsection (or extended remark) in §2 that recalls the key steps of the 2003 proof and confirms, via a brief case analysis, that no additional extremal configurations arise when k ≥ 3. This addition will be placed before the edge-switching arguments so that the subsequent comparisons rest on a self-contained foundation within the manuscript. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation builds on independent external structural theorem

full rationale

The paper explicitly builds its characterization on the structural classification of minimally (k,k)-edge-connected graphs from Hennayake, Lai, Li, and Mao (J. Graph Theory, 2003), whose authors are distinct from the present team. It then applies edge-switching and double-eigenvector techniques to maximize the spectral radius for fixed order or size, generalizing prior k=2 results from unrelated authors (Lou-Min-Huang 2023 and Chen-Guo 2019). No self-citation appears in the load-bearing steps, no parameter is fitted and then renamed as a prediction, and no equation reduces to its own input by definition. The cited 2003 framework is treated as an external, independently established result that classifies the admissible edge configurations, allowing the spectral arguments to proceed without circular reduction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work depends on a prior structural classification of minimally (k,k)-edge-connected graphs and on standard facts from spectral graph theory; no new free parameters or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption The structural framework of Hennayake, Lai, Li, and Mao (2003) classifies the possible configurations of minimally (k,k)-edge-connected graphs for general k.
    Abstract states that the authors build directly on this framework to apply edge-switching and eigenvector arguments.

pith-pipeline@v0.9.0 · 5776 in / 1342 out tokens · 47577 ms · 2026-05-22T02:25:38.066295+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

28 extracted references · 28 canonical work pages

  1. [1]

    Boesch, S

    F.T. Boesch, S. Chen, A generalization of line connectivity and optimally invulnerable graphs,SIAM J Appl Math,34(1978) 657–665

    work page 1978

  2. [2]

    Brualdi, A

    R.A. Brualdi, A. J. Hoffman, On the spectral radius of (0, 1)-matrices,Linear Algebra Appl.,65(1985) 133–146

    work page 1985

  3. [3]

    Brualdi, E.S

    R.A. Brualdi, E.S. Solheid, On the spectral radius of complementary acyclic matrices of zeros and one, SIAM J. Algebra Discrete Methods,7(1986) 265–272

    work page 1986

  4. [4]

    Chandran, Minimum cuts, girth and spectral threshold,Inform

    S.L. Chandran, Minimum cuts, girth and spectral threshold,Inform. Process. Lett.,89(2004) 105–110

    work page 2004

  5. [5]

    Chen, L.T

    X.D. Chen, L.T. Guo, On minimally 2-(edge)-connected graphs with extremal spectral radius,Discrete Math.,342(2019) 2092–2099

    work page 2019

  6. [6]

    Cioab˘ a, Eigenvalues and edge-connectivity of regular graphs,Linear Algebra Appl.,432(2010) 458–470

    S.M. Cioab˘ a, Eigenvalues and edge-connectivity of regular graphs,Linear Algebra Appl.,432(2010) 458–470

    work page 2010

  7. [7]

    Cvetovi´ c, P

    D. Cvetovi´ c, P. Rowlinson, S. Simi´ c, An introduction to the theory of graph spectra, Cambrige University Press, Cambridge, 2010. 18

    work page 2010

  8. [8]

    Fan, X.F

    D.D. Fan, X.F. Gu, H.Q. Lin, Spectral radius and edge-disjoint spanning trees,J. Graph Theory,104 (2023) 697–711

    work page 2023

  9. [9]

    Fan, X.F

    D.D. Fan, X.F. Gu, H.Q. Lin,l-connectivity,l-edge-connectivity and spectral radius of graphs,J Algebr Comb,60(2024) 929–947

    work page 2024

  10. [10]

    Gu, H.-J

    X.F. Gu, H.-J. Lai, P. Li, S.M. Yao, Edge-disjoint spanning trees, edge connectivity, and eigenvalues in graphs,J. Graph Theory,81(2016) 16–29

    work page 2016

  11. [11]

    Hennayake, H.-J

    K. Hennayake, H.-J. Lai, D.Y. Li, J.Z. Mao, Minimally (k, k)-edge-connected graphs,J. Graph Theory, 44(2003) 116–131

    work page 2003

  12. [12]

    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. B,81(2001) 177–183

    work page 2001

  13. [13]

    Horn, C.R

    R.A. Horn, C.R. Johnson, Matrix Analysis, Cambridge Univ. Press, Cambridge, 1985

    work page 1985

  14. [14]

    H.Q. Lin, B. Ning, B. Wu, Eigenvalues and triangles in graphs,Combin. Probab. Comput.,30(2) (2021) 258–270

    work page 2021

  15. [15]

    Lou, C.X

    Z.Z. Lou, C.X. He, A max-min problem on spectral radius and connectedness of graphs,Electron. J. Comb.,32(2025) Paper 2.33

    work page 2025

  16. [16]

    Z.Z. Lou, G. Min, Q.X. Huang, On the spectral radius of minimally 2-(edge)-connected graphs with given size,Electron. J. Comb.,30(2023) Paper 2.23

    work page 2023

  17. [17]

    Mader, ¨Uber minimaln-fach zusammenhangende, unendliche Graphen und ein Extremal problem, Archiv

    W. Mader, ¨Uber minimaln-fach zusammenhangende, unendliche Graphen und ein Extremal problem, Archiv. Math. (Basel),23(1972) 553–560

    work page 1972

  18. [18]

    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

  19. [19]

    W. Ning, M. Lu, K. Wang, Maximizing the spectral radius of graphs with fixed minimum degree and edge connectivity,Linear Algebra Appl.,540(2018) 138–148

    work page 2018

  20. [20]

    Nosal, Eigenvalues of Graphs (Master s thesis), University of Calgary, 1970

    E. Nosal, Eigenvalues of Graphs (Master s thesis), University of Calgary, 1970

    work page 1970

  21. [21]

    Oellermann, Explorations into graph connectivity,SAMS Notices,20(1988) 117–151

    O.R. Oellermann, Explorations into graph connectivity,SAMS Notices,20(1988) 117–151

    work page 1988

  22. [22]

    Stanley, A bound on the spectral radius of graphs witheedges,Linear Algebra Appl.,87(1987) 267–269

    R.P. Stanley, A bound on the spectral radius of graphs witheedges,Linear Algebra Appl.,87(1987) 267–269

    work page 1987

  23. [23]

    Wang, J-M

    Z.W. Wang, J-M. Guo, Some upper bounds on the spectral radius of a graph,Linear Algebra Appl., 601(2020) 101–112

    work page 2020

  24. [24]

    Wang, H.Q

    Y. Wang, H.Q. Lin, Y.Z. Tian, Extremal spectral radius and essential edge-connectivity,Discrete Math., 347(2024) 113948

    work page 2024

  25. [25]

    B. Wu, E. Xiao, Y. Hong, The spectral radius of trees onkpendant vertices,Linear Algebra Appl.,395 (2005) 343–349

    work page 2005

  26. [26]

    Xue, R.F

    J. Xue, R.F. Liu, J.L. Shu, Unimodality of principal eigenvector and its applications,Graphs Combin., 36(2020) 1177–1188. 19

    work page 2020

  27. [27]

    Zhai, H.Q

    M.Q. Zhai, H.Q. Lin, J.L. Shu, Spectral extrema of graphs with fixed size: cycles and complete bipartite graphs,European J. Combin.,95(2021) 103322

    work page 2021

  28. [28]

    Zhai, H.Q

    M.Q. Zhai, H.Q. Lin, J.L. Shu, Maximal spectral radius of minimallyk-(edge)-connected graphs,J. Graph Theory, (2025) 1–15. 20

    work page 2025