Three examples of a ground-breaking impact of the variable neighborhood search on investigations in graph theory


Dragoš Cvetković




The well known computer package {c AutoGraphiX} $($AGX$)$ uses the variable neighborhood search to solve extremal problems in graph theory. We describe how AGX, in its very first application $($cf. G. Caporossi, et al. $[$J. Chem. Inform. Comp. Sci. {\bf39} {\rm (1999), 984--996])}, has influenced substantially the study of graph energy. AGX helped very much in creating the spectral graph theory based on the signless Laplacian (see D. Cvetković, et al. $[$Publ. Inst. Math. $($Beograd$)$ {\bf81 (95)} {\rm (2007), 11--27])} and created some non-trivial conjectures on the largest eigenvalue of a graph (see M. Aouchiche, et al. $[$Europ. J. Oper. Res. {\bf 191} {\rm(3) (2008), 661--676])}