scientific article; zbMATH DE number 16299
[For the entire collection see Zbl 0719.00011.] This paper presents partial solutions to the following \(A\)-Cycle Problem: If \(G\) is a graph with a subset \(A\) of vertices and/or edges, find a cycle of \(G\) containing \(A\), an ``\(A\)-cycle, or show that none exists, i.e. ``\((G,A)\) is acyclic. If \(G\) is \(r\)-connected and \(| A|\leq r+2\), then \(G\) has an \(A\)- cycle or a particular disconnecting set, an ``\(A\)-separator. For the case that \(G\) has no such an \(A\)-separator, acyclic \((G,A)\) are characterized. The proofs of these results depend on a construction of minimal representatives of the class of graphs satisfying the hypotheses. Results are given for \(k\)-polytopal graphs and \(r\)-regular \(r\)-conncected graphs. Acyclicity is explained for 3-connected graphs with 10 and 11 vertices, or 4 edges.
- On circuits through five edges
- Toughness and edge-toughness
- One or two disjoint circuits cover independent edges. Lovász-Woodall conjecture
- Rooted topological minors on four vertices
- Local topological toughness and local factors
- On cycles through specified vertices
- An Improved Algorithm for Finding Cycles Through Elements
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3972952)