On Path-Pairability of Cartesian Product of Complete Bipartite Graphs

Gabor Meszaros

Published 2014-01-30, updated 2015-02-16Version 3

We study inheritance of path-pairability in the Cartesian product of graphs, and prove di?erent (such as additive and multiplicative) inheritance patterns of path-pairability, depending on the size of 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.