Bounds on isolated scattering number

Abstract

The isolated scattering number is a parameter that measures the vulnerability of networks. This measure is bounded by formulas depending on the independence number. We present new bounds on the isolated scattering number that can be calculated in polynomial time.

References

• Z. Chen, M. Dehmer, F. Emmert-Streib, and Y. Shi. Modern and interdisciplinary problems in network science: A translational research perspective. CRC Press, 2018. doi: 10.1201/9781351237307
• P. Erdős and T. Gallai. On the minimal number of vertices representing the edges of a graph. Magyar Tud. Akad. Mat. Kutató Int. Közl. 6 (1961), pp. 181–203. url: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.210.7468
• J. Harant and I. Schiermeyer. On the independence number of a graph in terms of order and size. Discrete Math. 232.1–3 (2001), pp. 131–138. doi: 10.1016/S0012-365X(00)00298-3
• E. Korach, T. Nguyen, and B. Peis. Subgraph characterization of red/blue-split graph and Kőnig Egerváry graphs. Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 2006, pp. 842–850. doi: 10.1145/1109557.1109650
• F. Li, Q. Ye, and Y. Sun. Proceedings of the 2016 Joint Conference of ANZIAM and Zhejiang Provincial Applied Mathematics Association, ANZPAMS-2016. Ed. by P. Broadbridge, M. Nelson, D. Wang, and A. J. Roberts. Vol. 58. ANZIAM J. 2017, E81–E97. doi: 10.21914/anziamj.v58i0.10993
• F. Li, Q. Ye, and X. Zhang. Isolated scattering number of split graphs and graph products. ANZIAM J. 58.3-4 (2017), pp. 350–358. doi: 10.1017/S1446181117000062
• E. R. Scheinerman and D. H. Ullman. Fractional graph theory. Dover Publications, 2011. url: https://www.ams.jhu.edu/ers/wp-content/uploads/2015/12/fgt.pdf
• S. Y. Wang, Y. X. Yang, S. W. Lin, J. Li, and Z. M. Hu. The isolated scattering number of graphs. Acta Math. Sinica (Chin. Ser.) 54.5 (2011), pp. 861–874. url: http://www.actamath.com/EN/abstract/abstract21097.shtml
• M. Xiao and H. Nagamochi. Exact algorithms for maximum independent set. Inform. and Comput. 255, Part 1 (2017), pp. 126–146. doi: 10.1016/j.ic.2017.06.001