On path-pairability in the Cartesian product of graphs

DOI10.7151/DMGT.1888MaRDI QIDQ726652zbMATH OpenOpenAlexFDO

Authors Gábor Mészáros

Publication date 13 July 2016

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/1401.7929

zbMATH Keywords

Cartesian product of graphspath-pairable graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph operations (line graphs, products, etc.) (05C76) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: We study inheritance of path-pairability in the Cartesian product of graphs, and prove different (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.

Recommendations

• The path-pairability number of product of stars
• On path-pairability of the finite grids
• On the maximum degree of path-pairable planar graphs
• Path-pairability of infinite planar grids
• scientific article; zbMATH DE number 1286752

Cites work

• Connectivity of Cartesian product graphs
• scientific article; zbMATH DE number 434691 (Why is no real title available?)
• scientific article; zbMATH DE number 90343 (Why is no real title available?)
• scientific article; zbMATH DE number 1286752 (Why is no real title available?)
• scientific article; zbMATH DE number 524123 (Why is no real title available?)
• scientific article; zbMATH DE number 1550912 (Why is no real title available?)
• scientific article; zbMATH DE number 6168325 (Why is no real title available?)
• Networks communicating for each pairing of terminals
• Note on the diameter of path-pairable graphs
• On connectivity of the cartesian product of two graphs
• Three-regular path pairable graphs

Cited in

(13)

• Linkage on the infinite grid
• Path-pairability of infinite planar grids
• On the maximum diameter of path-pairable graphs
• The path-pairability number of product of stars
• On the maximum degree of path-pairable planar graphs
• Terminal-pairability in complete bipartite graphs with non-bipartite demands. Edge-disjoint paths in complete bipartite graphs
• The terminal-pairability problem in complete bipartite graphs
• scientific article; zbMATH DE number 1933225 (Why is no real title available?)
• Note on terminal-pairability in complete grid graphs
• scientific article; zbMATH DE number 6264095 (Why is no real title available?)
• scientific article; zbMATH DE number 6291271 (Why is no real title available?)
• scientific article; zbMATH DE number 7656342 (Why is no real title available?)
• scientific article; zbMATH DE number 7709890 (Why is no real title available?)

This page was built for publication: On path-pairability in the Cartesian product of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q726652)