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

Fengwei Li, Qingfang Ye, Yuefang Sun


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.



Isolated Scattering Number, Interval graph, Consecutive clique arrangement

Full Text:



Remember, for most actions you have to record/upload into this online system
and then inform the editor/author via clicking on an email icon or Completion button.
ANZIAM Journal, ISSN 1446-8735, copyright Australian Mathematical Society.