On path-pairability in the Cartesian product of graphs

DOI10.7151/DMGT.1888zbMATH Open1339.05341arXiv1401.7929OpenAlexW2346811671MaRDI QIDQ726652FDOQ726652

Gábor Mészáros

Publication date: 13 July 2016

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

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.

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

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

zbMATH Keywords

Cartesian product of graphspath-pairable graphs

Mathematics Subject Classification ID

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

Cites Work

• On connectivity of the cartesian product of two graphs
• Title not available (Why is that?)
• Connectivity of Cartesian product graphs
• Three-regular path pairable graphs
• Title not available (Why is that?)
• Networks communicating for each pairing of terminals
• Title not available (Why is that?)
• Note on the diameter of path-pairable graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (13)

• On the maximum diameter of path-pairable graphs
• Linkage on the infinite grid
• Title not available (Why is that?)
• Title not available (Why is that?)
• The path-pairability number of product of stars
• On the maximum degree of path-pairable planar graphs
• Path-pairability of infinite planar grids
• The terminal-pairability problem in complete bipartite graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Note on terminal-pairability in complete grid graphs
• Terminal-pairability in complete bipartite graphs with non-bipartite demands. Edge-disjoint paths in complete bipartite graphs

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)