On Path-Pairability in the Cartesian Product of Graphs

• Autorzy: Gábor Mészáros
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

path-pairable graphs; Cartesian product of graphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2016
• Tom: 36
• Numer: 3
• Strony: 743-758

Daty

wydano

2016-08-01

otrzymano

2014-09-29

poprawiono

2015-11-04

zaakceptowano

2015-11-10

online

2016-07-06

Twórcy

autor

Gábor Mészáros

• Alfred Renyi Institute of Mathematics Central European University

Bibliografia

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

Identyfikatory

DOI

10.7151/dmgt.1888