Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Linear-time algorithms for scattering number and Hamilton-connectivity of interval graphs.

Broersma, H.J. and Fiala, J. and Golovach, P.A. and Kaiser, T. and Paulusma, D. and Proskurowski, A. (2015) 'Linear-time algorithms for scattering number and Hamilton-connectivity of interval graphs.', Journal of graph theory., 79 (4). pp. 282-299.

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.

Item Type:Article
Full text:(AM) Accepted Manuscript
Download PDF
(406Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1002/jgt.21832
Publisher statement:Broersma, H.J. and Fiala, J. and Golovach, P.A. and Kaiser, T. and Paulusma, D. and Proskurowski, A. (2014) 'Linear-time algorithms for scattering number and Hamilton-connectivity of interval graphs.', Journal of graph theory, 79(4): 282-299, which has been published in final form at http://dx.doi.org/10.1002/jgt.21832. This article may be used for non-commercial purposes in accordance With Wiley Terms and Conditions for self-archiving.
Date accepted:No date available
Date deposited:08 January 2015
Date of first online publication:28 October 2014
Date first made open access:No date available

Save or Share this output

Export:
Export
Look up in GoogleScholar