Polynomial algorithms for computing the isolated toughness of interval and split graphs

Fengwei Li, Qingfang Ye, Hajo Broersma, Xiaoyan Zhang*

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

47 Downloads (Pure)


The isolated toughness (Figure presented.) of a noncomplete graph G is defined as: (Figure presented.), 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 (Figure presented.). 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 (Figure presented.) for interval graphs and for split graphs, two well-studied special graph classes.

Original languageEnglish
Article numbere6345
JournalConcurrency Computation
Issue number17
Early online date24 Apr 2021
Publication statusPublished - 1 Aug 2023


  • factor
  • fractional factor
  • interval graph
  • isolated toughness
  • polynomial time algorithm
  • split graph
  • 22/1 OA procedure


Dive into the research topics of 'Polynomial algorithms for computing the isolated toughness of interval and split graphs'. Together they form a unique fingerprint.

Cite this