Advertisement
Published in:
04-01-2021
A sufficient condition for the unpaired k-disjoint path coverability of interval graphs
Published in: The Journal of Supercomputing | Issue 7/2021
Log inActivate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
Given disjoint source and sink sets, \(S = \{ s_1,\ldots ,s_k\}\) and \(T = \{t_1,\ldots , 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, \ldots , 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, \({{\,\mathrm{sc}\,}}(G)\), of an interval graph G of order \(n \ge 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 \({{\,\mathrm{sc}\,}}(G) \le -k\) is tight; moreover, the proof directly leads to a quadratic algorithm for building an unpaired k-disjoint path cover.