Note on the diameter of path-pairable graphs

DOI10.1016/J.DISC.2014.08.011MaRDI QIDQ465276zbMATH OpenOpenAlexFDO

Authors Gábor Mészáros

Publication date 31 October 2014

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

graph diameterpath-pairable graphs

Mathematics Subject Classification ID

Distance in graphs (05C12) Paths and cycles (05C38)

Abstract: A graph on $2k$ vertices is path-pairable if for any pairing of the vertices the pairs can be joined by edge-disjoint paths. The so far known families of path-pairable graphs have diameter of length at most 3. In this paper we present an infinite family of path-pairable graphs with diameter $d(G)=O(sqrtn)$ where $n$ denotes the number of vertices of the graph. We prove that our example is extremal up to a constant factor.

Recommendations

• On the maximum diameter of path-pairable graphs
• scientific article; zbMATH DE number 434691
• scientific article; zbMATH DE number 90343
• On the maximum degree of path-pairable planar graphs
• scientific article; zbMATH DE number 1286752

Cites work

• 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
• Three-regular path pairable graphs

Cited in

(8)

• The minimum size of graphs satisfying cut conditions
• On path-pairability of the finite grids
• On the maximum diameter of path-pairable graphs
• Terminal-pairability in complete bipartite graphs with non-bipartite demands. Edge-disjoint paths in complete bipartite graphs
• scientific article; zbMATH DE number 90343 (Why is no real title available?)
• scientific article; zbMATH DE number 1286752 (Why is no real title available?)
• Decomposition of graph into diametral paths
• On path-pairability in the Cartesian product of graphs

This page was built for publication: Note on the diameter of path-pairable graphs

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