On Path-Pairability in the Cartesian Product of Graphs

Gábor Mészáros

Discussiones Mathematicae Graph Theory (2016)

  • Volume: 36, Issue: 3, page 743-758
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Gábor Mészáros. "On Path-Pairability in the Cartesian Product of Graphs." Discussiones Mathematicae Graph Theory 36.3 (2016): 743-758. <http://eudml.org/doc/285877>.

@article{GáborMészáros2016,
abstract = {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.},
author = {Gábor Mészáros},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {path-pairable graphs; Cartesian product of graphs},
language = {eng},
number = {3},
pages = {743-758},
title = {On Path-Pairability in the Cartesian Product of Graphs},
url = {http://eudml.org/doc/285877},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Gábor Mészáros
TI - On Path-Pairability in the Cartesian Product of Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 3
SP - 743
EP - 758
AB - 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.
LA - eng
KW - path-pairable graphs; Cartesian product of graphs
UR - http://eudml.org/doc/285877
ER -

References

top
  1. [1] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (J. Wiley & Sons, New York, 2000). Zbl0963.05002
  2. [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. [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] Zbl0768.90022
  4. [4] R.J. Faudree, Properties in pairable graphs, New Zealand J. Math. 21 (1992) 91-106. Zbl0776.05058
  5. [5] R.J. Faudree, Some strong variations of connectivity, in: Combinatorics, Paul Erdős is Eighty, Bolyai Soc. Math. Stud. 1 (1993) 125-144. Zbl0791.05067
  6. [6] R.J. Faudree, A. Gyárfás and J. Lehel, Minimal path pairable graphs, Congr. Numer. 88 (1992) 111-128. Zbl0791.05058
  7. [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] Zbl0768.05061
  8. [8] R.J. Faudree, A. Gyárfás and J. Lehel, Path-pairable graphs, J. Combin. Math. Combin. Comput. 29 (1999) 145-157. Zbl0921.05043
  9. [9] E. Kubicka, G. Kubicki and J. Lehel, Path-pairable property for complete grids, Combin. Graph Theory Algorithms 1 (1999) 577-586. 
  10. [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. [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. [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] 

NotesEmbed ?

top

You must be logged in to post comments.