On the maximum induced forests of a connected cubic graph without triangles

✍ Scribed by Maolin Zheng; Xiaoyun Lu

• Publisher: Elsevier Science
• Year: 1990
• Tongue: English
• Weight: 438 KB
• Volume: 85
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(90)90165-e

✦ Synopsis

Let t(G) denote the cardinality of a maximum induced forest of a graph G with n vertices. For connected simple cubic graphs G without triangles, it is shown that r(G) 3 2n/3 except for two particular graphs. This lower bound is sharp and it improves a result due to J.A. Bondy, et al. [l]. Using this result, we show that Ewald Speckenmeyer's Conjecture, i.e. r(G) 2 2n/3 for all biconnected cubic graphs G with girth 4, is true, except for two particular graphs, which we describe.

1. Introducton

All graphs here are connected, simple, and undirected. G denotes a graph with n vertices. V(G) denotes the set of vertices of G. t(G) denotes the cardinality of a maximum induced forest of G. In this paper, we only consider cubic graphs with no triangles. The girth of a graph is the length of a shortest cycle in it.

Several previous papers study maximum induced forests of cubic graphs [l-5]. In [l, 21, the best possible bound of t(G) 2 ]5n/8] for any connected cubic graph was obtained. It follows easily from the main result of [3] that for any cubic graph C with girth at least 5, t(G) 2 2n/3. Speckenmeyer conjectured that this is still true for any biconnected cubic graph with girth 4. He also pointed out that if this conjecture is true then the lower bound, 2n/3, on t(G) is tight. In [l], it was shown that t(G) 2 (2n -1)/3 for connected cubic graphs without triangle. In this paper, we prove that t(G) 5 2n/3 for any cubic graph G without triangles, except for two cubic graphs with n = 8 and f(G) = 5. This lower bound is best possible and implies that Speckenmeyer's conjecture is true with two exceptions, and also improves a result of [l]. Our proof technique differs completely from those used in [l] and .

In Section 2, we prove that t(G) 2 [2n/3]. In Section 3, it is shown that t(G) 2 2n /3 with two exceptions.