Isolated Scattering Number Can be Computed in Polynomial Time for Interval Graphs

Abstract

The isolated scattering number of an incomplete connected graph\(~G\) is defined as \(\operatorname{isc}(G)=\max\{i(G-X)-|X|:X\in C(G)\}\), where\(~i(G-X)\) and\(~C(G)\), respectively, denote the number of components which are isolated vertices and the set of all separators of\(~G\). The isolated scattering number is a comparatively better parameter to measure the vulnerability of networks. We give a polynomial time algorithm to compute the isolated scattering number of interval graphs, a subclass of co-comparability graphs. Our result can also be used to compute isolated scattering number of proper interval graph. References

• C. A. Barefoot, R. Entringer and H. Swart. Vulnerability in graphs–-A comparative survey. J. Combin. Math. Combin. Comput. 1:12–22, 1987. https://www.researchgate.net/publication/266002676
• J. A. Bondy and U. S. R. Murty. Graph Theory with Applications. Macmillan, London and Elsevier, New york, 1976. http://101.96.10.59/www.iro.umontreal.ca/ hahn/IFT3545/GTWA.pdf
• K. S. Booth and G. S. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. System Sci. 13(3):335–379, 1976. doi:10.1016/S0022-0000(76)80045-1
• H. Broersma, J. Fiala, P. Golovach, T. Kaiser, D. Paulusma, A. Proskurowski. Linear-time algorithms for scattering number and hamilton-connectivity of interval graphs. J Graph Theory 79(4): 282-299, 2015. doi:10.1002/jgt.21832
• M. C. Carlisle, E. L. Loyd. On the k-coloring of intervals. LNCS 497: 90–101, 1991. doi:10.1016/0166-218X(95)80003-M
• V. Chvatal. Tough graphs and Hamiltonian circuits. Discrete Mathematics 5:215–228, 1973. doi:10.1016/j.disc.2006.03.011
• M. Cozzens, D. Moazzami and S. Stueckle. The tenacity of a graph. Proc. 7th International Conference on the Theory and Applications of Graphs, Wiley, New York, 1111–1122, 1995. http://101.96.10.59/www.iro.umontreal.ca/ hahn/IFT3545/GTWA.pdf
• J. Fabri. Automatic Storage Optimization. UMI Press Ann Arbor, MI, 1982. doi:10.1145/989393.989398
• P. C. Gilmore and A. J. Hoffman. A characterization of comparability graphs and of interval graphs. Canadian J. Math. 16(99):539–548, 1964. doi:10.1142/97898127969360006
• M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs. Academic Press, 1980. doi:10.1007/BF00390110
• H. A. Jung. On maximal circuits in finite graphs. Ann Discrete Math. 3:129–144, 1978. doi:10.1016/S0167-5060(08)70503-X
• J. R. Jungck, O. Dick, and A. G. Dick. Computer assisted sequencing, interval graphs and molecular evolution. Biosystem 15:259–273, 1982. doi:10.1016/0303-2647(82)90010-7
• T. Kloks and D. Kratschz. Listing all minimal separators of a graph. SIAM J. Comput. 27(3):605–613, 1998. doi:10.1137/S009753979427087X
• T. Kloks, D. Kratsch and J. Spinrad. Tree-width and path-width of co-comparability graphs of bounded dimension. Computing Science Note. Eindhoven University of Technology, Eindhoven, The Netherlands. 93-46. https:alexandria.tue.nl/extra1/wskrap/publichtml/9313455.pdf
• D. Kratsch, T. Klocks and H. Muller. Computing the toughness and the scattering number for interval and other graphs. IRISA resarch report. France, 1994. https://www.researchgate.net/publication/2646060
• F. W. Li. On isolated rupture degree of graphs. Utilitas Mathematica 96: 33–47, 2015. https://www.researchgate.net/publication/292526797
• F. W. Li. Isolated rupture degree of trees and gear graphs. Neural Network World 25(3): 287–300, 2015. doi:10.14311/NNW.2015.25.015
• F. W. Li and X. L. Li. Neighbor-scattering number can be computed in polynomial time for interval graphs. Computers and Mathematics with Applications 54(5):679–686, 2007. doi:10.1016/j.camwa.2007.02.006
• Y. K. Li, S. G. Zhang and X. L. Li. Rupture degree of graphs. Int. J. Comput. Math. 82(7):793–803, 2005. doi:10.1080/00207160412331336062
• T. Ohtsuki, H. Mori, Khu. E. S., T. Kashiwabara, T. Fujisawa. One dimensional logic gate assignment and interval graph. IEEE Trans. Circuits and Systems 26:675–684, 1979. doi:10.1109/TCS.1979.1084695
• S. Y. Wang, Y. X. Yang, S. W. Lin, J. Li and Z. M. Hu. The isolated scattering number of graphs. Acta Math. Sinica (in Chinese) 54(5):861–874, 2011. http://en.cnki.com.cn/Article_en/CJFDTotal-SXXB201105015.htm