A sufficient condition for the unpaired k-disjoint path coverability of interval graphs

摘要

Given disjoint source and sink sets, S = {s(1), ... , s(k)} and T = {t(1) , ... , t(k)}, in a graph G, an unpaired k-disjoint path cover joining S and T is a set of pairwise vertex-disjoint paths {P-1, ... , P-k} that altogether cover every vertex of the graph, in which P-i is a path from source s(i) to some sink t(j). In this paper, we prove that if the scattering number, sc (G), of an interval graph G of order n = 2k is less than or equal to -k, there exists an unpaired k-disjoint path cover joining S and T in G for any possible configurations of source and sink sets S and T of size k each. The bound sc (G) = -k is tight; moreover, the proof directly leads to a quadratic algorithm for building an unpaired k-disjoint path cover.