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.
@article{bwmeta1.element.doi-10_7151_dmgt_1888,
author = {G\'abor M\'esz\'aros},
title = {On Path-Pairability in the Cartesian Product of Graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {36},
year = {2016},
pages = {743-758},
zbl = {1339.05341},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1888}
}
Gábor Mészáros. On Path-Pairability in the Cartesian Product of Graphs. Discussiones Mathematicae Graph Theory, Tome 36 (2016) pp. 743-758. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1888/
[1] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (J. Wiley & Sons, New York, 2000). | Zbl 0963.05002
[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[WoS][Crossref]
[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[Crossref] | Zbl 0768.90022
[4] R.J. Faudree, Properties in pairable graphs, New Zealand J. Math. 21 (1992) 91-106. | Zbl 0776.05058
[5] R.J. Faudree, Some strong variations of connectivity, in: Combinatorics, Paul Erdős is Eighty, Bolyai Soc. Math. Stud. 1 (1993) 125-144. | Zbl 0791.05067
[6] R.J. Faudree, A. Gyárfás and J. Lehel, Minimal path pairable graphs, Congr. Numer. 88 (1992) 111-128. | Zbl 0791.05058
[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[Crossref] | Zbl 0768.05061
[8] R.J. Faudree, A. Gyárfás and J. Lehel, Path-pairable graphs, J. Combin. Math. Combin. Comput. 29 (1999) 145-157. | Zbl 0921.05043
[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[Crossref]
[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[Crossref]
[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[Crossref]