Geodesic
The Path-Pairability Number of Product of Stars
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 4, pp. 909-924.

Voir la notice de l'article provenant de la source Library of Science

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 ≤ i ≤ 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 
@article{DMGT_2019_39_4_a11,
     author = {Jobson, Adam S. and K\'ezdy, Andr\'e. and Lehel, Jen\H{o} and M\'esz\'aros, G\'abor},
     title = {The {Path-Pairability} {Number} of {Product} of {Stars}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {909--924},
     publisher = {mathdoc},
     volume = {39},
     number = {4},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a11/}
}
TY  - JOUR
AU  - Jobson, Adam S.
AU  - Kézdy, André.
AU  - Lehel, Jenő
AU  - Mészáros, Gábor
TI  - The Path-Pairability Number of Product of Stars
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 909
EP  - 924
VL  - 39
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a11/
LA  - en
ID  - DMGT_2019_39_4_a11
ER  - 
%0 Journal Article
%A Jobson, Adam S.
%A Kézdy, André.
%A Lehel, Jenő
%A Mészáros, Gábor
%T The Path-Pairability Number of Product of Stars
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 909-924
%V 39
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a11/
%G en
%F DMGT_2019_39_4_a11
Jobson, Adam S.; Kézdy, André.; Lehel, Jenő; Mészáros, Gábor. The Path-Pairability Number of Product of Stars. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 4, pp. 909-924. http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a11/

[1] L. Csaba, R.J. Faudree, A. Gyárfás, J. Lehel and R.H. Schelp, Networks communicating for each pairing of terminals, Networks 22 (1992) 615–626. doi:10.1002/net.3230220702

[2] R.J. Faudree, A. Gyárfás and J. Lehel, Three-regular path pairable graphs, Graphs Combin. 8 (1992) 45–52. doi:10.1007/BF01271707

[3] R.J. Faudree, A. Gyárfás and J. Lehel, Path-pairable graphs, J. Combin. Math. Combin. Comput. 29 (1999) 145–157.

[4] E. Győri, T.R. Mezei and G. Mészáros, Note on terminal-pairability in complete grid graphs, Discrete Math. 5 (2017) 988–990. doi:10.1016/j.disc.2017.01.014

[5] A. Huck, A sufficient condition for graphs to be weakly k-linked, Graphs Combin. 7 (1991) 323–351. doi:10.1007/BF01787639

[6] A.S. Jobson, A.E. Kézdy and J. Lehel, The path-pairability of the products of paths (2016), submitted.

[7] E. Kubicka, G. Kubicki, and J. Lehel, Path-pairable property for complete grids, in: Combinatorics, Graph Theory and Algorithms II (1999) 577–586.

[8] G. Mészáros, Linkedness and Path–Pairability in the Cartesian Product of Graphs, PhD Thesis (CEU, Budapest, 2015).

[9] G. Mészáros, On path-pairability in the Cartesian product of graphs, Discuss. Math. Graph Theory 36 (2016) 743–758. doi:10.7151/dmgt.1888