k-PATH GRAPHS: EXPERIMENTS AND CONJECTURES ABOUT ALGEBRAIC CONNECTIVITY AND α-INDEX

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 on [Discrete Applied Mathematics 164 (2014) 297-303] 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 ≤ n ≤ 26, 8 ≤ n ≤ 19, and 10 ≤ n ≤ 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.