### Abstract

We show 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(n + m) time algorithm for computing the scattering number of an interval graph with n vertices and m edges, which improves the O(n^3) 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(n + m) time.

Original language | English |
---|---|

Title of host publication | Graph-Theoretic Concepts in Computer Science |

Subtitle of host publication | 39th International Workshop, WG 2013, Lübeck, Germany, June 19-21, 2013, Revised Papers |

Editors | Andreas Brandstädt, Klaus Jansen, Rüdiger Reischuk |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 127-138 |

Number of pages | 12 |

ISBN (Electronic) | 978-3-642-45043-3 |

ISBN (Print) | 978-3-642-45042-6 |

DOIs | |

Publication status | Published - 2013 |

Event | 39th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2013 - Lübeck, Germany Duration: 19 Jun 2013 → 21 Jun 2013 Conference number: 39 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer Verlag |

Volume | 8165 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Workshop

Workshop | 39th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2013 |
---|---|

Abbreviated title | WG |

Country | Germany |

City | Lübeck |

Period | 19/06/13 → 21/06/13 |

### Keywords

- MSC-05C
- EWI-24425
- IR-89270
- METIS-302692
- Hamilton-connectivity
- Linear algorithm
- Scattering number
- Interval graph

## Fingerprint Dive into the research topics of 'Linear-time algorithms for scattering number and hamilton-connectivity of interval graphs'. Together they form a unique fingerprint.

## Cite this

Broersma, H. J., Fiala, J., Golovach, P. A., Kaiser, T., Paulusma, D., & Proskurowski, A. (2013). Linear-time algorithms for scattering number and hamilton-connectivity of interval graphs. In A. Brandstädt, K. Jansen, & R. Reischuk (Eds.),

*Graph-Theoretic Concepts in Computer Science: 39th International Workshop, WG 2013, Lübeck, Germany, June 19-21, 2013, Revised Papers*(pp. 127-138). (Lecture Notes in Computer Science; Vol. 8165). Berlin: Springer. https://doi.org/10.1007/978-3-642-45043-3_12