Three-regular path pairable graphs

DOI10.1007/BF01271707MaRDI QIDQ1187948zbMATH OpenFDO

Authors Ralph Faudree, András Gyárfás, Jeno Lehel

Publication date 3 August 1992

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

Full work available at URL https://doi.org/10.1007/BF01271707

zbMATH Keywords

3-regular graphboundspath pairable graphsweakly \(k\)-linked

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Review text

A graph \(G\) is \(k\)-path pairable if for any two disjoint sets of vertices \(\{x_ 1,x_ 2,\dots,x_ k\}\) and \(\{y_ 1,y_ 2,\dots,y_ k\}\) of \(G\) there are edge-disjoint paths \(P_ i\), \(1\leq i\leq k\), where \(P_ i\) is a path from \(x_ i\) to \(y_ i\). It is shown that for any positive integer \(k\) and for \(n\) sufficiently large, there is a 3-regular graph on \(n\) vertices that is \(k\)-path pairable. Such a graph can be constructed from a complete binary tree which has a root of degree three. The authors give upper and lower bounds for the minimum number of edges in a \(k\)-path pairable graph of order \(n\) with maximum degree at most 3, in terms of \(n\) and \(k\), for \(n\) sufficiently large.

Recommendations

• scientific article; zbMATH DE number 434691
• On k-pairable regular graphs
• scientific article; zbMATH DE number 90343
• Linkage on the infinite grid
• On the maximum degree of path-pairable planar graphs

Cites work

• A sufficient condition for graphs to be weakly \(k\)-linked
• Networks communicating for each pairing of terminals
• On Concentrators, Superconcentrators, Generalizers, and Nonblocking Networks
• On the Existence of Certain Configurations within Graphs and the 1-Skeletons of Polytopes
• Parallelism in Comparison Problems
• Superconcentrators

Cited in

(13)

• A communication problem and directed triple systems
• Note on the bisection width of cubic graphs
• The path-pairability number of product of stars
• Terminal-pairability in complete bipartite graphs with non-bipartite demands. Edge-disjoint paths in complete bipartite graphs
• Minimal 2-connected graphs satisfying the even cut condition
• scientific article; zbMATH DE number 434691 (Why is no real title available?)
• scientific article; zbMATH DE number 90343 (Why is no real title available?)
• Networks communicating for each pairing of terminals
• Note on the diameter of path-pairable graphs
• scientific article; zbMATH DE number 2165735 (Why is no real title available?)
• On k-pairable regular graphs
• On path-pairability in the Cartesian product of graphs
• Three-regular parts of four-regular graphs

This page was built for publication: Three-regular path pairable graphs

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