𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Subtrees and Subforests of Graphs

✍ Scribed by S. Brandt

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
299 KB
Volume
61
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we present sufficient edge-number and degree conditions for a graph to contain all forests of given size. The edge-number bound answers in the aflirmative a conjecture due to ErdΕ‘s and SΓ³s. Furthermore, we will give improved bounds for specified spanning subtrees of graphs. 1994 Academic Press, Inc.

πŸ“œ SIMILAR VOLUMES

Induced subtrees in graphs of large chro
Induced subtrees in graphs of large chromatic number
✍ A. GyΓ‘rfΓ‘s; E. Szemeredi; Zs. Tuza πŸ“‚ Article πŸ“… 1980 πŸ› Elsevier Science 🌐 English βš– 469 KB

Our paper proves special eases of the following conjecture: for any fined tr~,e "J~ there exists a natural number f = fiT) ~o that every triangle-free graph of chromatic number ] T) contains T as au induced subgraph. The main ;csult concerns the case when T has radius two.

The decomposition of trees into subtrees
The decomposition of trees into subtrees
✍ Yair Caro πŸ“‚ Article πŸ“… 1984 πŸ› John Wiley and Sons 🌐 English βš– 332 KB

## Abstract A necessary condition for the decomposition of a tree __T__ into subtrees, each isomorphic to a tree from a given set of trees is presented. We also present a characterization of the set of trees for which the condition is sufficient. Many examples are given.

Transversals of subtree hypergraphs and
Transversals of subtree hypergraphs and the source location problem in digraphs
✍ Jan van den Heuvel; Matthew Johnson πŸ“‚ Article πŸ“… 2008 πŸ› John Wiley and Sons 🌐 English βš– 134 KB

## Abstract A hypergraph __H__ = (__V__,__E__) is a subtree hypergraph if there is a tree __T__ on __V__ such that each hyperedge of __E__ induces a subtree of __T__. Since the number of edges of a subtree hypergraph can be exponential in __n__ = |__V__|, one can not always expect to be able to fin