7-connected graphs are 4-ordered

DOI10.1016/J.JCTB.2019.07.002MaRDI QIDQ2284739zbMATH OpenOpenAlexWikidataFDO

Authors Rose McCarty, Yan Wang, Xingxing Yu

Publication date 15 January 2020

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

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

zbMATH Keywords

\(k\)-ordered graphsconnectivitycyclesgraph linkages

Mathematics Subject Classification ID

Paths and cycles (05C38) Connectivity (05C40)

Abstract: A graph $G$ is $k$-ordered if for any distinct vertices $v_1,v_2,ldots,v_{k}inV(G)$, it has a cycle through $v_1,v_2,ldots,v_k$ in order. Let $f(k)$ denote the minimum integer so that every $f(k)$-connected graph is $k$-ordered. The first non-trivial case of determining $f(k)$ is when $k=4$, where the previously best known bounds are $7leqf(4)leq40$. We prove that in fact $f(4)=7$.

Recommendations

• 4-connected maximal planar graphs are 4-ordered
• Survey of results on \(k\)-ordered graphs
• 4-connected triangulations and 4-orderedness
• Onk-ordered graphs
• On 3-regular 4-ordered graphs

Cites work

• 2-linked graphs
• 4-connected maximal planar graphs are 4-ordered
• 4-connected triangulations and 4-orderedness
• A look at cycles containing specified elements of a graph
• A note on Lovász removable path conjecture
• A Polynomial Solution to the Undirected Two Paths Problem
• An extremal problem for H‐linked graphs
• An improved linear edge bound for graph linkages
• Disjoint paths in graphs
• Disjoint paths in graphs. I: 3-planar graphs and basic obstructions
• Disjoint paths in graphs. II: A special case
• Disjoint paths in graphs. III: Characterization
• Eine Verallgemeinerung des n-fachen Zusammenhangs für Graphen
• Graph connectivity after path removal
• Highly linked graphs
• scientific article; zbMATH DE number 3494318 (Why is no real title available?)
• In abstrakten Graphen vorhandene vollständige 4‐Graphen und ihre Unterteilungen
• k-ordered Hamiltonian graphs
• Linkage for the diamond and the path with four vertices
• Non-separating subgraphs after deleting many disjoint paths
• On Sufficient Degree Conditions for a Graph to be k-linked
• Survey of results on \(k\)-ordered graphs
• The extremal function for 3-linked graphs

Cited in

(7)

• A seven connected finite H-space is fourteen connected
• 4-connected maximal planar graphs are 4-ordered
• Linking four vertices in graphs of large connectivity
• Optimal connectivity for fat-triangle linkages
• Every 5-connected planar triangulation is 4-ordered Hamiltonian
• Connectivity for kite-linked graphs
• On regular 2-path Hamiltonian graphs

This page was built for publication: 7-connected graphs are 4-ordered

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