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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.