Variable neighbourhood search for connected graphs of fixed order and size with minimal spectral radius
In this study we consider connected graphs of fixed order 𝑛 and size 𝑚 that minimize the largest eigenvalue of the adjacency matrix, also known as the spectral radius. Such graphs are called minimizers. The motivation for this research lies in the fact that the spectral radius plays a significant ro...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2024-01-01
|
| Series: | Kuwait Journal of Science |
| Subjects: | |
| Online Access: | https://www.sciencedirect.com/science/article/pii/S2307410823001839 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849694833385406464 |
|---|---|
| author | Kristina Kostić Zorica Dražić Aleksandar Savić Zoran Stanić |
| author_facet | Kristina Kostić Zorica Dražić Aleksandar Savić Zoran Stanić |
| author_sort | Kristina Kostić |
| collection | DOAJ |
| description | In this study we consider connected graphs of fixed order 𝑛 and size 𝑚 that minimize the largest eigenvalue of the adjacency matrix, also known as the spectral radius. Such graphs are called minimizers. The motivation for this research lies in the fact that the spectral radius plays a significant role in modelling virus propagation in complex networks, in the sense that a smaller spectral radius ensures a better virus protection in the network modelled by the corresponding graph. We conjecture that vertex degrees of a minimizer are as equal as possible, i.e. belong to {⌊2𝑚∕𝑛⌋, ⌈2𝑚∕𝑛⌉}. The conjecture is confirmed for graphs with at most 10 vertices by the total enumeration, and some classes of graphs are resolved theoretically. In general, exact determining of minimizers is quite difficult and computationally exhaustive, and thus we propose a long-scale variable neighbourhood search as an alternative approach. We employ this heuristic search for selected instances concerning graphs with at most 100 vertices, and as a result we always obtain a graph with required vertex degrees. The search efficiently results in solutions that are (in a precise sense) close to the optimal ones, i.e. to minimizers. |
| format | Article |
| id | doaj-art-1e3410d08ba74428bc5ae03f93b99f68 |
| institution | DOAJ |
| issn | 2307-4116 |
| language | English |
| publishDate | 2024-01-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Kuwait Journal of Science |
| spelling | doaj-art-1e3410d08ba74428bc5ae03f93b99f682025-08-20T03:19:57ZengElsevierKuwait Journal of Science2307-41162024-01-01511100142https://doi.org/10.1016/j.kjs.2023.10.009Variable neighbourhood search for connected graphs of fixed order and size with minimal spectral radiusKristina Kostić0https://orcid.org/0000-0002-0693-2488Zorica Dražić1https://orcid.org/0000-0002-3434-6734Aleksandar Savić2Zoran Stanić3https://orcid.org/0000-0002-4949-4203Faculty of Mathematics, University of Belgrade, SerbiaFaculty of Mathematics, University of Belgrade, SerbiaFaculty of Mathematics, University of Belgrade, SerbiaFaculty of Mathematics, University of Belgrade, SerbiaIn this study we consider connected graphs of fixed order 𝑛 and size 𝑚 that minimize the largest eigenvalue of the adjacency matrix, also known as the spectral radius. Such graphs are called minimizers. The motivation for this research lies in the fact that the spectral radius plays a significant role in modelling virus propagation in complex networks, in the sense that a smaller spectral radius ensures a better virus protection in the network modelled by the corresponding graph. We conjecture that vertex degrees of a minimizer are as equal as possible, i.e. belong to {⌊2𝑚∕𝑛⌋, ⌈2𝑚∕𝑛⌉}. The conjecture is confirmed for graphs with at most 10 vertices by the total enumeration, and some classes of graphs are resolved theoretically. In general, exact determining of minimizers is quite difficult and computationally exhaustive, and thus we propose a long-scale variable neighbourhood search as an alternative approach. We employ this heuristic search for selected instances concerning graphs with at most 100 vertices, and as a result we always obtain a graph with required vertex degrees. The search efficiently results in solutions that are (in a precise sense) close to the optimal ones, i.e. to minimizers.https://www.sciencedirect.com/science/article/pii/S2307410823001839spectral radiusvertex degreevirus propagationvariable neighbourhood search |
| spellingShingle | Kristina Kostić Zorica Dražić Aleksandar Savić Zoran Stanić Variable neighbourhood search for connected graphs of fixed order and size with minimal spectral radius Kuwait Journal of Science spectral radius vertex degree virus propagation variable neighbourhood search |
| title | Variable neighbourhood search for connected graphs of fixed order and size with minimal spectral radius |
| title_full | Variable neighbourhood search for connected graphs of fixed order and size with minimal spectral radius |
| title_fullStr | Variable neighbourhood search for connected graphs of fixed order and size with minimal spectral radius |
| title_full_unstemmed | Variable neighbourhood search for connected graphs of fixed order and size with minimal spectral radius |
| title_short | Variable neighbourhood search for connected graphs of fixed order and size with minimal spectral radius |
| title_sort | variable neighbourhood search for connected graphs of fixed order and size with minimal spectral radius |
| topic | spectral radius vertex degree virus propagation variable neighbourhood search |
| url | https://www.sciencedirect.com/science/article/pii/S2307410823001839 |
| work_keys_str_mv | AT kristinakostic variableneighbourhoodsearchforconnectedgraphsoffixedorderandsizewithminimalspectralradius AT zoricadrazic variableneighbourhoodsearchforconnectedgraphsoffixedorderandsizewithminimalspectralradius AT aleksandarsavic variableneighbourhoodsearchforconnectedgraphsoffixedorderandsizewithminimalspectralradius AT zoranstanic variableneighbourhoodsearchforconnectedgraphsoffixedorderandsizewithminimalspectralradius |