Polynomial algorithms for computing the isolated toughness of interval and split graphs
Fengwei Li, Qingfang Ye, Hajo J. Broersma, Xiaoyan Zhang · Concurrency and Computation Practice and Experience · 2021
Abstract The isolated toughness of a noncomplete graph G is defined as: , where C(G) is the collection of all vertex cutsets of G and i(G − Y) stands for the number of isolated vertices in G − Y. If G is a complete graph, we set . This isolated toughness parameter is closely related to the existence of factors and fractional factors in graphs. These factors and fractional factors are well‐studied within graph theory, and have various applications in several fields related to computer science. In this article, we pay our attention to the computational complexity of computing the isolated toughness. We present polynomial algorithms for computing the exact value of for interval graphs and for split graphs, two well‐studied special graph classes.