pith. sign in

arxiv: 2511.21524 · v2 · submitted 2025-11-26 · 💻 cs.DM · math.CO

k-path graphs: experiments and conjectures about algebraic connectivity and α-index

Rafael L. de Paula , Claudia M. Justel , Carla S. Oliveira , Milena S. Carauba This is my paper

Pith reviewed 2026-05-17 04:38 UTC · model grok-4.3

classification 💻 cs.DM math.CO
keywords k-path graphsalgebraic connectivityalpha-indexLaplacian eigenvaluesA_alpha matrixextremal graphsgraph conjectures
0
0 comments X

The pith

Exhaustive searches on k-path graphs up to order 26 lead to conjectures on extremal structures for algebraic connectivity and the alpha-index.

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

The authors develop a method to generate all non-isomorphic k-path graphs for small values of n. They compute the algebraic connectivity and alpha-index for each such graph and identify the ones with extreme values. Patterns in these extremal graphs form the basis for conjectures about the general form of k-path graphs that maximize or minimize these quantities for larger orders. Sympathetic readers would care if these conjectures turn out to be true because they would give a simple way to determine or bound these important graph eigenvalues without full computation for each instance.

Core claim

Using generated lists of all non-isomorphic 2-path graphs for n from 6 to 26, 3-path graphs for n from 8 to 19, and 4-path graphs for n from 10 to 18, exhaustive searches identify consistent extremal graphs for the algebraic connectivity of the Laplacian and the largest eigenvalue of the A_alpha matrix. These identifications support conjectures describing the structure of the k-path graphs that achieve the algebraic connectivity and alpha-index extrema.

What carries the argument

The complete lists of non-isomorphic k-path graphs obtained through the generation process based on prior work, serving as the finite search space for finding eigenvalue extrema at each order n.

Load-bearing premise

The extremal structures observed in the computed range of n continue to hold as the extremal ones for all larger n.

What would settle it

Discovery of a k-path graph with order greater than 26 whose algebraic connectivity exceeds that of all graphs matching the conjectured extremal structure for its order.

Figures

Figures reproduced from arXiv: 2511.21524 by Carla S. Oliveira, Claudia M. Justel, Milena S. Carauba, Rafael L. de Paula.

Figure 1
Figure 1. Figure 1: Construction’s phases for k-path lists with k ∈ {2, 3, 4} and fixed and bounded n Given G = P8 ∨ K3 of order 11 (see [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗
Figure 3
Figure 3. Figure 3: P8 ∨ K3 The objective of Algorithm in Section 5 of [18] (see transcription in Algorithm 1 below) is to generate a restricted normalized sequences with at most k + 1 10 [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 2
Figure 2. Figure 2: Details 2-path graphs lists; formats: for lists, [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: 2-generalized fan of order 7 u1 u4 u2 u3 u6 u5 u7 [PITH_FULL_IMAGE:figures/full_fig_p020_3.png] view at source ↗
read the original abstract

This work presents conjectures about eigenvalues of matrices associated with $k$-path graphs, the algebraic connectivity, defined as the second smallest eigenvalue of the Laplacian matrix, and the $\alpha$-index, as the largest eigenvalue of the $A_{\alpha}$-matrix. For this purpose, a process based in Pereira et al., is presented to generate lists of $k$-path graphs containing all non-isomorphic 2-paths, 3-paths, and 4-paths of order $n$, for $6 \leq n \leq 26, 8 \leq n \leq 19$, and $10 \leq n \leq 18$, respectively. Using these lists, exhaustive searches for extremal graphs of fixed order for the mentioned eigenvalues were performed. Based on the empirical results, conjectures are suggested about the structure of extremal $k$-path graphs for these eigenvalues.

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 manuscript presents a generation procedure, based on prior work, to produce complete lists of non-isomorphic k-path graphs for 6≤n≤26 (k=2), 8≤n≤19 (k=3) and 10≤n≤18 (k=4). It then reports exhaustive computation of the algebraic connectivity (second-smallest Laplacian eigenvalue) and the α-index (largest eigenvalue of the A_α matrix) over these lists, identifies the extremal graphs in each case, and formulates conjectures on the structural form of the graphs attaining the extrema.

Significance. If the conjectures prove correct, the work supplies explicit structural descriptions of extremal k-path graphs for two standard spectral invariants, which could guide subsequent theoretical investigations. The computational foundation is strengthened by the exhaustive enumeration of all non-isomorphic instances within the stated ranges; all reported quantities are obtained directly from the adjacency and Laplacian matrices with no fitted parameters or self-referential constructions.

major comments (1)
  1. The conjectures (final section) assert that particular k-path graphs remain extremal for algebraic connectivity and the α-index for all n larger than the enumerated ranges. The supporting data stop at n=26 (k=2), n=19 (k=3) and n=18 (k=4); no asymptotic argument, proof sketch, or verification for any n beyond these bounds is supplied. A single counterexample at larger order would falsify the general statements, so the conjectures require an explicit qualification of their computational scope.
minor comments (2)
  1. The description of the generation algorithm would be clearer if it included a short pseudocode fragment or explicit statement of how isomorphism checking is performed.
  2. Tables listing the extremal graphs should indicate both the eigenvalue value and the order n for each entry to facilitate direct comparison across k.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the thorough review and for the recommendation of minor revision. The single major comment correctly identifies that our conjectures would benefit from an explicit statement of their computational basis. We will revise the manuscript to qualify the conjectures accordingly while preserving the empirical findings and the structural descriptions they suggest.

read point-by-point responses

  1. Referee: The conjectures (final section) assert that particular k-path graphs remain extremal for algebraic connectivity and the α-index for all n larger than the enumerated ranges. The supporting data stop at n=26 (k=2), n=19 (k=3) and n=18 (k=4); no asymptotic argument, proof sketch, or verification for any n beyond these bounds is supplied. A single counterexample at larger order would falsify the general statements, so the conjectures require an explicit qualification of their computational scope.

    Authors: We agree that the conjectures as phrased in the final section could be read as claiming validity for all larger n without additional support. In the revised manuscript we will add a qualifying sentence at the beginning of the conjecture statements, explicitly noting that they are formulated on the basis of exhaustive enumeration for 6≤n≤26 (k=2), 8≤n≤19 (k=3) and 10≤n≤18 (k=4), and that their validity beyond these ranges remains open to theoretical proof or further computational verification. This change makes the computational scope transparent without altering the reported extremal graphs or the conjectured structural forms. revision: yes

Circularity Check

0 steps flagged

No circularity: conjectures derived from direct matrix computations on enumerated graphs

full rationale

The paper enumerates all non-isomorphic k-path graphs up to finite orders using a generation process, computes algebraic connectivity (second-smallest Laplacian eigenvalue) and α-index (largest A_α eigenvalue) directly via matrix operations, and proposes conjectures about extremal structures based on the observed patterns. No parameters are fitted such that any 'prediction' reduces to the input by construction, no self-definitional loops exist in the eigenvalue definitions, and the cited generation method (Pereira et al.) is external to the central empirical claims rather than a load-bearing self-citation chain. The derivation chain consists of explicit enumeration followed by standard linear-algebra computations, making the work self-contained against external benchmarks with no reduction of outputs to inputs by definition.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters are fitted, no new axioms are introduced beyond standard linear algebra over graphs, and no invented entities are postulated; the work rests on exhaustive enumeration of a finite set of graphs.

pith-pipeline@v0.9.0 · 5469 in / 1027 out tokens · 21688 ms · 2026-05-17T04:38:52.402374+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

27 extracted references · 27 canonical work pages

  1. [1]

    Old and new results on algebraic connectivity of graphs

    Abreu, N.M.M de, “Old and new results on algebraic connectivity of graphs", Linear Algebra and its Applications 423(1) (2007) 53-73

    work page 2007

  2. [2]

    Ordering trees and graphs with few cycles by algebraic connectivity

    Abreu, N.M.M. de, Justel, C.M., Rojo, O., Trevisan, V., “Ordering trees and graphs with few cycles by algebraic connectivity", Linear Algebra and its Applications 458 (2014) 429-453

    work page 2014

  3. [3]

    An introduction to chordal graphs and clique trees

    Blair, J.R.S., Peyton, B., “An introduction to chordal graphs and clique trees”. In: George, J.A., Gilbert, J. R., Liu, J. W. H. (Eds.),Graph theory and sparse matrix computation. Springer Verlag, IMA 56, 1-30, 1993

    work page 1993

  4. [4]

    House of Graphs: A database of interesting graphs

    Brinkmann, G., Coolsaet, K., Goedgebeur, J., Mélot, H., “House of Graphs: A database of interesting graphs", Discrete Applied Mathe- matics 161 (2013) 311-314

    work page 2013

  5. [5]

    House of Graphs 2.0: A databaseofinterestinggraphsandmore

    Coolsaet, K., D’hondt, S., Goedgebeur, J. “House of Graphs 2.0: A databaseofinterestinggraphsandmore", DiscreteAppliedMathematics 325 (2023) 97-107

    work page 2023

  6. [6]

    Cvetković, D., “Signless Laplacians and line graphs’, Bull. Acad. Serbe Sci. Arts, Cl. Sci. Math. Natur., Sci. Math 131 (2005) 85-92

    work page 2005

  7. [7]

    Graph Theory

    Diestel, R., “Graph Theory", Springer Berlin, Heidelberg (2001)

    work page 2001

  8. [8]

    Algebraic connectivity of graphs

    Fiedler, M., “Algebraic connectivity of graphs", Czechoslovak Mathe- matical Journal 23(2) (1973) 298–305

    work page 1973

  9. [9]

    Algorithmic Graph Theory and Perfect Graphs

    Golumbic, M.C., “Algorithmic Graph Theory and Perfect Graphs", Aca- demic Press (1980). 21

    work page 1980

  10. [10]

    Isoperimetric graph partitioning for image segmentation

    Grady, L., Schwartz, E.L., “Isoperimetric graph partitioning for image segmentation", IEEE Transactions on Pattern Analysis and Machine Intelligence 28:3 (2006) 469-475

    work page 2006

  11. [11]

    Ikemoto, Y. Nishimura, K., Mizutama, Y., Sasaki, T., Jindai, M., “Net- work Connectivity Control of Mobile Robots by Fast Position Estima- tions and Laplacian Kernel, Journal of Robotics and Mechatronics 32(2) (2020) 422-436

    work page 2020

  12. [12]

    Grafos Outerplanares Maximais e Grafos 2-Caminho com Conectividade Algébrica Máxima

    Justel, C.M., de Paula, R. L., Ribeiro, D.B.B., “Grafos Outerplanares Maximais e Grafos 2-Caminho com Conectividade Algébrica Máxima", Anais do LV Simpósio Brasileiro de Pesquisa Operacional (2023) 160333

    work page 2023

  13. [13]

    On theAα-spectra of graphs

    Lin, H., Xue, J. Shu, J., “On theAα-spectra of graphs". Linear Algebra and its Applications 556 (2018) 210-229

    work page 2018

  14. [14]

    Subclasses ofk-trees: Char- acterization and recognition

    Markenzon, L., Justel, C.M., Paciornik, N., “Subclasses ofk-trees: Char- acterization and recognition", Discrete Applied Mathematics 154 (2006) 811-825

    work page 2006

  15. [15]

    Generalizating path and fan graphs: Subcoloring and toughness

    Markenzon, L., Waga, C. F.E.M., “Generalizating path and fan graphs: Subcoloring and toughness". Pesquisa Operacional 34:1 (2014) 107-116

    work page 2014

  16. [16]

    Nikiforov, N., “Merging theA- andQ-spectral theories, Applicable Anal- ysis and Discrete Mathematics 11 (2017) 81-107

    work page 2017

  17. [17]

    On (k+1)-line graphs ofk-trees and their nullities

    Oliveira, A.S.S., Aguieiras, M.A.F., Vinagre, C.T.M., Markenzon, L., “On (k+1)-line graphs ofk-trees and their nullities", Linear Algebra and its Applications 614 (2021) 244-255

    work page 2021

  18. [18]

    Pereira, P. R. da C., Garcia, A., Markenzon, L., “Generating and count- ing unlabeledk-path graphs’, Discrete Applied Mathematics 164 (2014) 297-303

    work page 2014

  19. [19]

    Classes of graphs with restricted inter- val models

    Proskurowski, A., Telle, J.A., “Classes of graphs with restricted inter- val models", Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only] 3(4) (1999) 167-176

    work page 1999

  20. [20]

    An Atlas of Graphs

    Read, R.C., Wilson, R.J., “An Atlas of Graphs", Oxford Science Publi- cations (1998) 22

    work page 1998

  21. [21]

    On Simple Characterixations ofk-Trees

    Rose, D., “On Simple Characterixations ofk-Trees", Discrete Mathe- matics 7 (1974) 317-322

    work page 1974

  22. [22]

    Three conjectures in extremal spectral graph the- ory

    Tait, M., Tobin, J., “Three conjectures in extremal spectral graph the- ory", Journal of Combinatorial Theory, Series B 126 (2017) 137-161

    work page 2017

  23. [23]

    On algebraic connectivity of directed scale-free networks

    Takanobu I., Cai, K., “On algebraic connectivity of directed scale-free networks", Journal of the Franklin Institute 355:16 (2018) 8065-8078

    work page 2018

  24. [24]

    ThesignlessLaplacianspectral radius of bounded degree graphs on surfaces

    Yu, G., Feng, L., Ilić, A., Stevanović, D., “ThesignlessLaplacianspectral radius of bounded degree graphs on surfaces", Applicable Analysis and Discrete Mathematics 9:2 (2015) 332-346

    work page 2015

  25. [25]

    The extremalα-index of outerplanar and planar graphs

    Yu, Z., Kang, L.,Liu, L., Shan, E., “The extremalα-index of outerplanar and planar graphs", Applied Mathematics and Computation 343 (2019) 90-99

    work page 2019

  26. [26]

    On the signless Laplacian spectra ofk-trees

    Zhang, M., Li, S., "On the signless Laplacian spectra ofk-trees", Linear Algebra and its Applications 467 (2015) 136-148. 23

    work page 2015

  27. [27]

    Appendix 7.1. Maximum and minimum algebraic connectivity of 3-paths and 4-paths of fixed ordern n max a(G) 3-pathGing6format C, color sequence forG 8 2.2679 G~[xhc 1 2 1 2 9 2.1981 H~[xhcp 1 2 1 2 1 10 2.1522 I~[xhcpKG 1 2 1 2 1 2 11 2.1206 J~[xhcpKH__ 1 2 1 2 1 2 1 12 2.0979 K~[xhcpKH_e@ 1 2 1 2 1 2 1 2 13 2.0810 L~[xhcpKH_e@K@ 1 2 1 2 1 2 1 2 1 14 2.068...

    work page 1981