Global connectivity and expansion: long cycles and factors in f-connected graphs
A graph \(G\) is called \(f\)-connected if every separation \((A,B)\) of \(G\) with \(| A\setminus B| \leq| B\setminus A| \) satisfies \(| A\cap B| \geq f(| A\setminus B| )\) where \(f:\mathbb{N}\setminus\{0\}\rightarrow\mathbb{R}\) is a (usually non-decreasing) function. The authors investigate relations between the \(f\)-connectedness of a graph and properties of its substructures. They prove that an \(f\)-connected graph contains a cycle of length linear in \(n\) if \(f\) is any linear function, contains a 1-factor and a 2-factor if \(f(k)\geq 2k+1\), and contains a Hamilton cycle if \(f(k)\geq2(k+1)^2\). Their conjecture that linear growth of \(f\) suffices to imply Hamiltonicity is still open.
- On connencted \([g,f+1]\)-factors in graphs
- scientific article; zbMATH DE number 3961655
- Degree and stability number condition for the existence of connected factors in graphs
- Long cycles and 3-connected spanning subgraphs of bounded degree in 3- connected \(K_{1,d}\)-free graphs
- Connected factors in graphs -- a survey
- Matchings in regular graphs from eigenvalues
- Long cycles in subgraphs of (pseudo)random directed graphs
- Ramsey goodness of paths
- A survey on Hamilton cycles in directed graphs
- The size Ramsey number of a directed path
- Ramsey goodness of cycles
- Cycle packing
- Decomposing random graphs into few cycles and edges
- On sufficient conditions for spanning structures in dense graphs
- Hamilton cycles in highly connected and expanding graphs
- Nearly Hamilton cycles in sublinear expanders and applications
- Ramsey goodness of paths versus unbalanced graphs
- Graph theory. Abstracts from the workshop held January 5--10, 2025
- Separating the edges of a graph by cycles and by subdivisions of K₄
- Ramsey numbers of cycles in random graphs
This page was built for publication: Global connectivity and expansion: long cycles and factors in \(f\)-connected graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2495692)
