𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Induced forests in cubic graphs

✍ Scribed by William Staton

Publisher
Elsevier Science
Year
1984
Tongue
English
Weight
151 KB
Volume
49
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Bounds are obtained for the number of vertices in a largest induced forest in a cubic graph with large girth. In particular, as girth increases without bound, the ratio of the number of vertices in a largest induced forest to the number of vertices in the whole graph approaches 3/4.

The point arboficity of a graph, introduced in [5], is the smallest number of subsets into which the vertices may be partitioned so that each subset induces a forest. Related to this concept is the parameter f(G) introduced for a graph G by Albertson and Berman in [2]. Informally, f(G) is the relative size of a largest possible induced forest in G. More precisely, if G is a graph with p vertices,

πŸ“œ SIMILAR VOLUMES

Large induced forests in sparse graphs
Large induced forests in sparse graphs
✍ Noga Alon; Dhruv Mubayi; Robin Thomas πŸ“‚ Article πŸ“… 2001 πŸ› John Wiley and Sons 🌐 English βš– 148 KB

## Abstract For a graph __G__, let __a__(__G__) denote the maximum size of a subset of vertices that induces a forest. Suppose that __G__ is connected with __n__ vertices, __e__ edges, and maximum degree Ξ”. Our results include: (a) if Δ ≀ 3, and __G__ ≠ __K__~4~, then __a__(__G__) β‰₯ __n__β€‰βˆ’β€‰e/4β€‰βˆ’β€‰1

Induced matchings in cubic graphs
Induced matchings in cubic graphs
✍ Peter HorΓ‘k; He Qing; William T. Trotter πŸ“‚ Article πŸ“… 1993 πŸ› John Wiley and Sons 🌐 English βš– 527 KB

## Abstract In this paper, we show that the edge set of a cubic graph can always be partitioned into 10 subsets, each of which induces a matching in the graph. This result is a special case of a general conjecture made by ErdΓΆs and NeΕ‘etΕ™il: For each __d__ β‰₯ 3, the edge set of a graph of maximum de

On the maximum induced forests of a conn
On the maximum induced forests of a connected cubic graph without triangles
✍ Maolin Zheng; Xiaoyun Lu πŸ“‚ Article πŸ“… 1990 πŸ› Elsevier Science 🌐 English βš– 438 KB

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

Path factors in cubic graphs
Path factors in cubic graphs
✍ Ken-ichi Kawarabayashi; Haruhide Matsuda; Yoshiaki Oda; Katsuhiro Ota πŸ“‚ Article πŸ“… 2002 πŸ› John Wiley and Sons 🌐 English βš– 67 KB