zbMATH — the first resource for mathematics

On feedback vertex sets and nonseparating independent sets in cubic graps. (English) Zbl 0657.05042
A subset F, J of nodes of G (undirected, connected with n nodes) is a FVS (feedback vertex set) if G-F is a forest, a NSIS (nonseparating independent set) if no two nodes of J are adjacent and G-J is connected, respectively. The equation \(f(G)=n/2-z(G)+1,\) where f, z denotes the cardinality of min FVS, max NSIS, respectively, and two new upper bounds for f(G) are derived for cubic graphs G.
Reviewer: J.Štulc

05C35 Extremal problems in graph theory
Full Text: DOI
[1] Garey, SIAM J. Appl. Math. 32 pp 826– (1977)
[2] On vertex-induced forests in cubic graphs. Proceedings of the 5th South East Conference on Combinatorics, Graph Theory, and Computing (1974) 501–512.
[3] and , Some further approximation algorithms for the vertex cover problem. Proceedings of the 8th Colloquium on Trees in Algebra and Programming (1983) 341–349.
[4] Simonovits, Acta Math. Acad. Sci. Hung. 18 pp 191– (1967)
[5] Bounds on feedback vertex sets of undirected cubic graphs. Coll. Math. Soc. Janos Bolyai 42. Algebra, Combinatorics and Logic in Computer Science (1983) 719–729.
[6] Untersuchungen zum Feedback Vertex Set Problem in ungerichteten Graphen. Ph.D. thesis, Paderborn (1983). · Zbl 0534.68046
[7] Staton, Discrete Math. 49 pp 175– (1984)
[8] and , Über Kreise in Graphen. VEB Deutscher Verlag der Wissenschaften, Berlin (1974). · Zbl 0288.05101
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.