Authors: A.S. Jobson, A.E. Kézdy, J. Lehel, G. Mészáros Title: The path -pairability number of products of stars Source: Discussiones Mathematicae Graph Theory Received 12.12.2016, Revised 27.12.2017, Accepted 27.12.2017, doi: 10.7151/dmgt.2114 | |
Abstract: 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, s_{i},t_{i}, 1≤ i≤ k, there exist pairwise edge-disjoint s_{i},t_{i}-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. | |
Keywords: path-pairability, weak linkage, Cartesian product, star-like network, telecommunications network | |
Links: |