$k$-path graphs: experiments and conjectures about algebraic connectivity and $α$-index
This work addresses a specific problem in graph theory for researchers studying spectral properties, but it is incremental as it builds on existing methods to propose conjectures without proving them.
The paper tackles the problem of identifying extremal k-path graphs for algebraic connectivity and α-index eigenvalues by generating exhaustive lists of non-isomorphic graphs and performing searches, leading to conjectures about their structure based on empirical results for orders up to 26.
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 $α$-index, as the largest eigenvalue of the $A_α$-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.