Cycles Intersecting Edge-Cuts of Prescribed Sizes

DOI10.1137/070683635zbMath1229.05174OpenAlexW2253259020MaRDI QIDQ3393422

Riste Škrekovski, Tomáš Kaiser

Publication date: 20 August 2009

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/501f2dfaebb535a029aa3785626d15f10d334bd0

zbMATH Keywords

graphdominating cycleedge-cutcoverable set

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (14)

A 7/6-approximation algorithm for the minimum 2-edge connected subgraph problem in bipartite cubic graphs ⋮ Excluded $t$-Factors in Bipartite Graphs: Unified Framework for Nonbipartite Matchings, Restricted 2-Matchings, and Matroids ⋮ On Dominating Even Subgraphs in Cubic Graphs ⋮ Hamilton cycles in 5-connected line graphs ⋮ Pairwise Disjoint Perfect Matchings in r-Edge-Connected r-Regular Graphs ⋮ Circuits of length 5 in 2-factors of cubic graphs ⋮ Balanced generic circuits without long paths ⋮ Shorter tours and longer detours: uniform covers and a bit beyond ⋮ The salesman's improved tours for fundamental classes ⋮ Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs ⋮ Star Chromatic Index ⋮ Small snarks with large oddness ⋮ The fractional chromatic number of triangle-free subcubic graphs ⋮ A note on antisymmetric flows in graphs

This page was built for publication: Cycles Intersecting Edge-Cuts of Prescribed Sizes