Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs

Broersma, H.J.; Fiala, J.; Golovach, P.A.; Kaiser, T.; Paulusma, D.; Proskurowski, A.

Abstract

We prove that for all inline image an interval graph is inline image-Hamilton-connected if and only if its scattering number is at most k. This complements a previously known fact that an interval graph has a nonnegative scattering number if and only if it contains a Hamilton cycle, as well as a characterization of interval graphs with positive scattering numbers in terms of the minimum size of a path cover. We also give an inline image time algorithm for computing the scattering number of an interval graph with n vertices and m edges, which improves the previously best-known inline image time bound for solving this problem. As a consequence of our two results, the maximum k for which an interval graph is k-Hamilton-connected can be computed in inline image time.

Citation

Broersma, H., Fiala, J., Golovach, P., Kaiser, T., Paulusma, D., & Proskurowski, A. (2015). Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs. Journal of Graph Theory, 79(4), 282-299. https://doi.org/10.1002/jgt.21832

• Journal Article Type: Article
• Online Publication Date: Oct 28, 2014
• Publication Date: Aug 1, 2015
• Deposit Date: Dec 20, 2014
• Publicly Available Date: Jan 8, 2015
• Journal: Journal of Graph Theory
• Print ISSN: 0364-9024
• Electronic ISSN: 1097-0118
• Publisher: Wiley
• Peer Reviewed: Peer Reviewed
• Volume: 79
• Issue: 4
• Pages: 282-299
• DOI: https://doi.org/10.1002/jgt.21832
• Public URL: https://durham-repository.worktribe.com/output/1439478