Geodesic
On Path-Pairability in the Cartesian Product of Graphs
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 3, pp. 743-758.

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

We study the inheritance of path-pairability in the Cartesian product of graphs and prove additive and multiplicative inheritance patterns of path-pairability, depending on the number of vertices in the Cartesian product. We present path-pairable graph families that improve the known upper bound on the minimal maximum degree of a path-pairable graph. Further results and open questions about path-pairability are also presented.
Keywords: path-pairable graphs, Cartesian product of graphs 
@article{DMGT_2016_36_3_a16,
     author = {M\'esz\'aros, G\'abor},
     title = {On {Path-Pairability} in the {Cartesian} {Product} of {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {743--758},
     publisher = {mathdoc},
     volume = {36},
     number = {3},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a16/}
}
TY  - JOUR
AU  - Mészáros, Gábor
TI  - On Path-Pairability in the Cartesian Product of Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 743
EP  - 758
VL  - 36
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a16/
LA  - en
ID  - DMGT_2016_36_3_a16
ER  - 
%0 Journal Article
%A Mészáros, Gábor
%T On Path-Pairability in the Cartesian Product of Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 743-758
%V 36
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a16/
%G en
%F DMGT_2016_36_3_a16
Mészáros, Gábor. On Path-Pairability in the Cartesian Product of Graphs. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 3, pp. 743-758. http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a16/

[1] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (J. Wiley & Sons, New York, 2000).

[2] W.-S. Chiue and B.-S. Shieh, On connectivity of the Cartesian product of two graphs, Appl. Math. Comput. 102 (1999) 129-137. doi:10.1016/S0096-3003(98)10041-3

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

[4] R.J. Faudree, Properties in pairable graphs, New Zealand J. Math. 21 (1992) 91-106.

[5] R.J. Faudree, Some strong variations of connectivity, in: Combinatorics, Paul Erdős is Eighty, Bolyai Soc. Math. Stud. 1 (1993) 125-144.

[6] R.J. Faudree, A. Gyárfás and J. Lehel, Minimal path pairable graphs, Congr. Numer. 88 (1992) 111-128.

[7] 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

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

[9] E. Kubicka, G. Kubicki and J. Lehel, Path-pairable property for complete grids, Combin. Graph Theory Algorithms 1 (1999) 577-586.

[10] G. Mésáros, On linkedness in the Cartesian product of graphs, Period. Math. Hungar., to appear. doi:10.1007/s10998-016-0113-8

[11] G. Mészáros, Note on the diameter of path-pairable graphs, Discrete Math. 337 (2014) 83-86. doi:10.1016/j.disc.2014.08.011

[12] J. Xu and C. Yang, Connectivity of Cartesian product graphs, Discrete Math. 306 (2006) 159-165. doi:10.1016/j.disc.2005.11.010