
AbstractWe prove that for all an interval graph is ‐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 time algorithm for computing the scattering number of an interval graph with n vertices and m edges, which improves the previously best‐known 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 time.
FOS: Computer and information sciences, Connectivity, Eulerian and Hamiltonian graphs, EWI-24425, Hamilton-connectivity, Scattering number, minimum size of a path cover, IR-89270, 2024 OA procedure, METIS-302692, Graph algorithms (graph-theoretic aspects), Hamilton cycle, Computer Science - Data Structures and Algorithms, Interval graph, Data Structures and Algorithms (cs.DS), Linear algorithm, MSC-05C
FOS: Computer and information sciences, Connectivity, Eulerian and Hamiltonian graphs, EWI-24425, Hamilton-connectivity, Scattering number, minimum size of a path cover, IR-89270, 2024 OA procedure, METIS-302692, Graph algorithms (graph-theoretic aspects), Hamilton cycle, Computer Science - Data Structures and Algorithms, Interval graph, Data Structures and Algorithms (cs.DS), Linear algorithm, MSC-05C
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 19 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
