Computing the Weighted Isolated Scattering Number of Interval Graphs in Polynomial Time. (10th March 2019) - Li, Fengwei; Zhang, Xiaoyan; Ye, Qingfang; Sun, Yuefang
Abstract : The scattering number and isolated scattering number of a graph have been introduced in relation to Hamiltonian properties and network vulnerability, and the isolated scattering number plays an important role in characterizing graphs with a fractional 1-factor. Here we investigate the computational complexity of one variant, namely, the weighted isolated scattering number. We give a polynomial time algorithm to compute this parameter of interval graphs, an important subclass of perfect graphs.