On the maximum degree of path-pairable planar graphs

MaRDI QIDQ2415080zbMATH OpenFDO

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

Publication date 20 May 2019

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.06068, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i2p18

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Vertex degrees (05C07) Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Connectivity (05C40)

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 investigate the behaviour of the maximum degree in path-pairable planar graphs. We show that any $n$-vertex path-pairable planar graph must contain a vertex of degree linear in $n$.

Review text

Summary: A graph is path-pairable if for any pairing of its vertices there exist edge-disjoint paths joining the vertices in each pair. We investigate the behaviour of the maximum degree in path-pairable planar graphs. We show that any \(n\)-vertex path-pairable planar graph must contain a vertex of degree linear in \(n\). Our result generalizes to graphs embeddable on a surface of finite genus.

Recommendations

• scientific article; zbMATH DE number 434691
• On the maximum diameter of path-pairable graphs
• Bounds on path connectivity
• scientific article; zbMATH DE number 1286752
• Path-pairability of infinite planar grids

Cites work

• A Separator Theorem for Planar Graphs
• A sufficient condition for a graph to be weakly k-linked
• A sufficient condition for graphs to be weakly \(k\)-linked
• An improved linear edge bound for graph linkages
• Graph minors. XIII: The disjoint paths problem
• Highly linked graphs
• scientific article; zbMATH DE number 434691 (Why is no real title available?)
• scientific article; zbMATH DE number 16298 (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 1301961 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• Networks communicating for each pairing of terminals
• Note on terminal-pairability in complete grid graphs
• On path-pairability in the Cartesian product of graphs
• On the complexity of the disjoint paths problem
• The disjoint paths problem in quadratic time

Cited in

(11)

• Three-regular path pairable graphs
• Path-pairability of infinite planar grids
• Structure and pancyclicity of maximal planar graphs with diameter two
• On the maximum diameter of path-pairable graphs
• scientific article; zbMATH DE number 1286752 (Why is no real title available?)
• Note on the diameter of path-pairable graphs
• Path transferability of planar graphs
• The degree/diameter problem in maximal planar bipartite graphs
• The degree/diameter problem in maximal planar bipartite graphs
• On the maximality of some pairs of p-t degrees
• On path-pairability in the Cartesian product of graphs

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

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