2013/01/24 by Hajo Broersma, Jiří Fiala, Broersma, Hajo +10
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Theory and Algorithms #Graph theory and applications #Interconnection Networks and Systems #Topological and Geometric Data Analysis #cs.DS
paper · pdf · doi:10.48550/arxiv.1301.5953
openalex publication_date 2013/01/24 · arxiv created 2013/01/25 · arxiv updated 2013/01/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Hung and Chang showed that for all k>=1 an interval graph has a path cover of size at most k if and only if its scattering number is at most k. They also showed that an interval graph has a Hamilton cycle if and only if its scattering number is at most 0. We complete this characterization by proving that for all k<=-1 an interval graph is -(k+1)-Hamilton-connected if and only if its scattering number is at most k. We also give an O(m+n) time algorithm for computing the scattering number of an interval graph with n vertices an m edges, which improves the O(n4) time bound of Kratsch, Kloks and Müller. As a consequence of our two results the maximum k for which an interval graph is k-Hamilton-connected can be computed in O(m+n) time.