On bags and bugs (Q2482094)

A \textit{bag} \(Bag_{p,q}\) and a \textit{bug} \(Bug_{p,q_1,q_2}\) are graphs obtained from a complete graph \(K_p\) by replacing an edge \(uv\) with a path \(P_q\) joining \(u,v\) and by disjoint paths \(P_{q_1}\) attached at \(u\) and \(P_{q_2}\) attached at \(v\). The largest eigenvalue of the adjacency matrix of a graph is its \textit{index}. The authors consider two extremal problems of a type proposed in [\textit{R. A. Brualdi, E. S. Solheid}, ``On the spectral radius of complementary acyclic matrices of zeros and ones.'' SIAM J. Algebraic Discrete Methods 7, 265--272 (1986; Zbl 0591.05051)]. Theorems 4 and 5 characterize, respectively in terms of bags and bugs, graphs on \(n\) vertices of maximum index having respectively a prescribed diameter, and a prescribed radius, proving structural conjectures obtained using the AutoGraphiX (AGX) software system (cf., [\textit{M. Aouchiche, J. M. Bonnefoy, A. Fidahoussen, G. Caporossi, P. Hansen, L. Hiesse, J. Lacheré, A. Monhait}, Variable neighborhood search for extremal graphs. XIV: The AutoGraphiX 2 system. Liberti, Leo et al., Global optimization. From theory to implementation. (New York), NY: Springer. Nonconvex Optimization and Its Applications 84, 281-310 (2006; Zbl 1100.90052)]).