Path-pairability of infinite planar grids

For a given integer k ≥ 1 , a graph G with at least 2 k vertices is called k -path-pairable, if for any set of k disjoint pairs of vertices, s i , t i , 1 ≤ i ≤ k , there exist pairwise edge-disjoint s i , t i -paths in G . The path-pairability numberis the largest k such that G is k -path-pairable....

Full description

Saved in:
Bibliographic Details
Published in:Periodica mathematica Hungarica 2021-12, Vol.83 (2), p.220-232
Main Authors: Jobson, Adam S., Kézdy, André E., Lehel, Jenő
Format: Article
Language:English
Subjects:
Apexes
Euclidean geometry
Graph theory
Integers
Mathematics
Mathematics and Statistics
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:For a given integer k ≥ 1 , a graph G with at least 2 k vertices is called k -path-pairable, if for any set of k disjoint pairs of vertices, s i , t i , 1 ≤ i ≤ k , there exist pairwise edge-disjoint s i , t i -paths in G . The path-pairability numberis the largest k such that G is k -path-pairable. Bounds on the path-pairability number are given here if G is the graph of infinite integer grids in the Euclidean plane. We prove that the path-pairability number of the integer quadrant is 4, and we show that the integer half-plane is 6-path-pairable and at most 7-path-pairable.
ISSN:0031-5303
1588-2829
DOI:10.1007/s10998-021-00381-2