Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6874147 | Information Processing Letters | 2018 | 6 Pages |
Abstract
For k fixed, a graph G is k-path-pairable, if for any set of k disjoint pairs of vertices, si,ti, 1â¤iâ¤k, there exist pairwise edge-disjoint si,ti-paths in G. Bounds on path-pairability are given here if G is the graph of the infinite integer grid in the Euclidean plane (vertices of G are the points of integer coordinates and two vertices are adjacent if and only if their Manhattan distance is 1). We prove that G is 10-path-pairable and at most 14-path-pairable. Related results and conjectures are summarized also for the integer halfplane, for the positive integer quadrant and for finite grids.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Adam S. Jobson, André E. Kézdy, JenÅ Lehel,