On bags and bugs
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)]).
- On the signless Laplacian index and radius of graphs
- A conjecture on the diameter and signless Laplacian index of graphs
- Sharp bounds on the spectral radii of uniform hypergraphs concerning diameter or clique number
- Majorants and minorants for the classes of graphs with fixed diameter and number of vertices
- Unified extremal results for vertex-degree-based graph invariants with given diameter
- Anticritical graphs
- scientific article; zbMATH DE number 3652373 (Why is no real title available?)
- scientific article; zbMATH DE number 3758364 (Why is no real title available?)
- scientific article; zbMATH DE number 740754 (Why is no real title available?)
- scientific article; zbMATH DE number 3255492 (Why is no real title available?)
- On some interconnections between combinatorial optimization and extremal graph theory
- On the Spectral Radius of Complementary Acyclic Matrices of Zeros and Ones
- On the spectral radius of graphs with cut vertices
- Some results on the index of unicyclic graphs
- Variable neighborhood search
- Variable neighborhood search for extremal graphs 3
- Variable neighborhood search for extremal graphs. I: The AutoGraphiX system
- Variable neighborhood search for extremal graphs. V: Three ways to automate finding conjectures
- Variable neighbourhood search: Methods and applications
- Maximizing the spectral radius of bicyclic graphs with fixed girth
- Asymptotic results on the spectral radius and the diameter of graphs
- Variations on the bagdomain theme
- Some results on the distance and distance signless Laplacian spectral radius of graphs and digraphs
- On the \(\alpha\)-index of graphs with pendent paths
- The maximum spectral radius of graphs without friendship subgraphs
- Sharp bounds on the spectral radii of uniform hypergraphs concerning diameter or clique number
- Spectral conditions for graphs to be \(k\)-Hamiltonian or \(k\)-path-coverable
- A sufficient \(Q\)-spectral condition for a graph to be \(\beta\)-deficient involving minimum degree
- On the minimum eccentric distance sum of bipartite graphs with some given parameters
- On minimally 2-(edge)-connected graphs with extremal spectral radius
- A conjecture on the diameter and signless Laplacian index of graphs
- The bag and the string: are they opposed?
- Maximizing the signless Laplacian spectral radius of \(k\)-connected graphs with given diameter
- Computing the maximal signless Laplacian index among graphs of prescribed order and diameter
- On the spectral radius of tricyclic graphs with a fixed diameter
- Maximizing the signless Laplacian spectral radius of graphs with given diameter or cut vertices
- scientific article; zbMATH DE number 3845184 (Why is no real title available?)
- The maximum Perron roots of digraphs with some given parameters
- Spectral radius of graphs
- Spectral conditions for graphs to be \(\beta\)-deficient involving minimum degree
- On the maximum spectral radius of multipartite graphs
- What’s in the Bag?
- Spectral conditions for some graphical properties
- The spectral radius of edge chromatic critical graphs
- Further results on the reciprocal degree distance of graphs
- On the \(\alpha\)-spectral radius of unicyclic and bicyclic graphs with a fixed diameter
- Graphs with the minimum spectral radius for given independence number
- On spectral radii of clique and coclique extension of path and cycle
- Resolution of AutoGraphiX conjectures relating the index and matching number of graphs
- Maximizing the spectral radius of k-connected graphs with given diameter
- A survey of automated conjectures in spectral graph theory
- Variable neighbourhood search: methods and applications
This page was built for publication: On bags and bugs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2482094)
