On the maximum diameter of path-pairable graphs

DOI10.1007/S00373-019-02099-YMaRDI QIDQ2287755zbMATH OpenOpenAlexWikidataFDO

Authors António Girão, Kamil Popielarz, Gábor Mészáros, Richard Snyder

Publication date 21 January 2020

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

diameterextremal graph theorypath-pairability

Mathematics Subject Classification ID

Distance in graphs (05C12) Extremal problems in graph theory (05C35)

Abstract: A graph is path-pairable if for any pairing of its vertices there exist edge disjoint paths joining the vertices in each pair. We obtain sharp bounds on the maximum possible diameter of path-pairable graphs which either have a given number of edges, or are c- degenerate. Along the way we show that a large family of graphs obtained by blowing up a path is path-pairable, which may be of independent interest.

Recommendations

• Note on the diameter of path-pairable graphs
• On the maximum degree of path-pairable planar graphs
• scientific article; zbMATH DE number 434691
• On path-pairability of the finite grids
• scientific article; zbMATH DE number 1286752

Cites work

• Highly linked 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?)
• Networks communicating for each pairing of terminals
• Note on terminal-pairability in complete grid graphs
• Note on the diameter of path-pairable graphs
• On path-pairability in the Cartesian product of graphs
• On the maximum degree of path-pairable planar graphs

Cited in

(8)

• The monotonic diameter of the perfect matching and shortest path polytopes
• Structure and pancyclicity of maximal planar graphs with diameter two
• On the maximum degree of path-pairable planar graphs
• scientific article; zbMATH DE number 434691 (Why is no real title available?)
• Wide diameter and minimum length of disjoint Menger path systems
• Note on the diameter of path-pairable graphs
• The degree/diameter problem in maximal planar bipartite graphs
• The degree/diameter problem in maximal planar bipartite graphs

This page was built for publication: On the maximum diameter of path-pairable graphs

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