scientific article; zbMATH DE number 16299

From MaRDI portal
Publication:3972952





[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.











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)