✦ LIBER ✦

Large induced forests in sparse graphs

✍ Scribed by Noga Alon; Dhruv Mubayi; Robin Thomas

Publisher: John Wiley and Sons
Year: 2001
Tongue: English
Weight: 148 KB
Volume: 38
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.1028

No coin nor oath required. For personal study only.

✦ Synopsis

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/4 and this is sharp for all permissible e ≡ 3 (mod 4); and (b) if Δ ≥ 3, then a(G) ≥ α(G) + (n − α(G))/(Δ − 1)^2^. Several problems remain open. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 113–123, 2001

📜 SIMILAR VOLUMES

Induced forests in cubic graphs

✍ William Staton 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 151 KB

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 arbof

Maximal induced trees in sparse random g

Maximal induced trees in sparse random graphs

✍ Tomasz łuczak; Zbigniew Palka 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 493 KB

A study of the orders of maximal induced trees in a random graph G, with small edge probability p is given. In particular, it is shown that the giant component of almost every G,, where p = c/n and c > 1 is a constant, contains only very small maximal trees (that are of a specific type) and very lar

On large matchings and cycles in sparse

On large matchings and cycles in sparse random graphs

✍ A.M Frieze 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 666 KB

Let k be a fixed positive integer. A graph H has property Mk if it contains [½k] edge disjoint hamilton cycles plus a further edge disjoint matching which leaves at most one vertex isolated, if k is odd. Let p = c/n, where c is a large enough constant. We show that G,,p a.s. contains a vertex induce

The number of connected sparsely edged g

The number of connected sparsely edged graphs. IV large nonseparable graphs

✍ E. M. Wright 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 306 KB

The number of nonseparable graphs on n labeled points and q lines is u(n, 9). In the second paper of this series an exact formula for u(n, n + k) was found for general n and successive (small) k. The method would give an asymptotic approximation for fixed k as n + 30. Here an asymptotic approximatio

The largest induced tree in a sparse ran

The largest induced tree in a sparse random graph

✍ W. Fernandez de la Vega 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 192 KB 👁 2 views

The author proved that, for c > 1, the random graph G(n, p ) on n vertices with edge probability p = c / n contains almost always an induced tree on at least q n ( 1 -o( 1)) vertices, where L Y ~ is the positive root of the equation CLY = log( 1 + c'a). It is shown here that if c is sufficiently lar

A family of sparse graphs of large sum n

A family of sparse graphs of large sum number

✍ Nora Hartsfield; W.F. Smyth 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 440 KB

Given an integer r ~>0, let G, =(V,, E) denote a graph consisting of a simple finite undirected graph G=(V,E) of order n and size m together with r isolated vertices K,. Then ]Vl=n, I V,l=n+r, and tEl=re. Let L://,--,7/+ denote a labelling of the vertices of G, with distinct positive integers. Then