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: | |
| Look up in GoogleScholar |
