The extremal function for 3-linked graphs

DOI10.1016/J.JCTB.2007.11.008MaRDI QIDQ947723zbMATH OpenOpenAlexFDO

Authors Robin Thomas, Paul Wollan

Publication date 7 October 2008

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jctb.2007.11.008

zbMATH Keywords

connectivitydisjoint pathsgraph linkages

Mathematics Subject Classification ID

Connectivity (05C40)

Review text

A graph \(G\) is \(k\)-linked if for every set of \(2k\) distinct vertices \(\{s_1,s_2,\dots,s_k,t_1,t_2,\dots,t_k\}\) of \(G\) there exist \(k\) disjoint path \(P_1,P_2,\dots,P_k\) such that the endpoints of \(P_i\) are \(s_i\) and \(t_i\) for \(1\leq i\leq k\). A natural question is whether or not there is a function \(f(k)\) such that every \(f(k)\)-connected graph is \(k\)-linked. In this paper the authors prove that every 6-connected graph of order \(n\) with at least \(5n-14\) edges is 3-linked. This bound is best possible because there exist 6-connected graphs of order \(n\) with \(5n-15\) edges that are not 3-linked for arbitrarily large \(n\).

Recommendations

• Extremal 3-connected graphs
• The extremal function for three disjoint theta graphs.
• The extremal function for bipartite linklessly embeddable graphs
• The extremal functions for triangle-free graphs with excluded minors
• The extremal function and Colin de Verdière graph parameter
• An extremal problem on contractible edges in 3-connected graphs
• An extremal problem for H‐linked graphs
• An extremal function for contractions of graphs
• On the extremal function for graph minors
• scientific article; zbMATH DE number 3987311

Cites work

• 2-linked graphs
• A Polynomial Solution to the Undirected Two Paths Problem
• An extremal function for contractions of graphs
• An improved linear edge bound for graph linkages
• Disjoint paths in graphs
• Eine Verallgemeinerung des n-fachen Zusammenhangs für Graphen
• Graph minors and linkages
• Graph minors. IX: Disjoint crossed paths
• Graph minors. XIII: The disjoint paths problem
• Highly linked graphs
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• scientific article; zbMATH DE number 3865318 (Why is no real title available?)
• scientific article; zbMATH DE number 16300 (Why is no real title available?)
• On Sufficient Degree Conditions for a Graph to be k-linked
• On the Existence of Certain Configurations within Graphs and the 1-Skeletons of Polytopes

Cited in

(15)

• The extremal functions for triangle-free graphs with excluded minors
• An improved linear edge bound for graph linkages
• An improved linear connectivity bound for tournaments to be highly linked
• Rooted topological minors on four vertices
• Characterization of \((m, n)\)-linked planar graphs
• 7-connected graphs are 4-ordered
• The extremal function for bipartite linklessly embeddable graphs
• Highly linked graphs
• Optimal connectivity for fat-triangle linkages
• Linkage for the diamond and the path with four vertices
• Combined degree and connectivity conditions for H-linked graphs
• scientific article; zbMATH DE number 1439448 (Why is no real title available?)
• Connectivity for kite-linked graphs
• A graph minor condition for graphs to be \(k\)-linked
• Some recent progress and applications in graph minor theory

This page was built for publication: The extremal function for 3-linked graphs

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