A.S. Jobson, A.E. Kézdy, J. Lehel, G. Mészáros
The path -pairability number of products of stars
Discussiones Mathematicae Graph Theory
Received 12.12.2016, Revised 27.12.2017, Accepted 27.12.2017, doi: 10.7151/dmgt.2114

The study of a graph theory model of certain telecommunications network problems lead to the concept of path-pairability, a variation of weak linkedness of graphs. A graph G is k-path-pairable if for any set of 2k distinct vertices, si,ti, 1≤ i≤ k, there exist pairwise edge-disjoint si,ti-paths in G, for 1\le i\le k. The path-pairability number is the largest k such that G is k-path-pairable. Cliques, stars, the Cartesian product of two cliques (of order at least three) are `fully pairable'; that is ⌊ n/2⌋-pairable, where n is the order of the graph. Here we determine the path-pairability number of the Cartesian product of two stars.
path-pairability, weak linkage, Cartesian product, star-like network, telecommunications network