𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Maximum induced trees in graphs

✍ Scribed by Paul Erdös; Michael Saks; Vera T Sós

Publisher
Elsevier Science
Year
1986
Tongue
English
Weight
952 KB
Volume
41
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Maximum induced matchings in graphs
Maximum induced matchings in graphs
✍ Jiping Liu; Huishan Zhou 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 218 KB

We provide a formula for the number of edges of a maximum induced matching in a graph. As applications, we give some structural properties of (k + 1 )K2-free graphs, construct all 2K2-free graphs, and count the number of labeled 2K2-free connected bipartite graphs.

Rooted induced trees in triangle-free gr
Rooted induced trees in triangle-free graphs
✍ Florian Pfender 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 68 KB

## Abstract For a graph __G__, let __t__(__G__) denote the maximum number of vertices in an induced subgraph of __G__that is a tree. Further, for a vertex __v__∈__V__(__G__), let __t__(__G, v__) denote the maximum number of vertices in an induced subgraph of __G__that is a tree, with the extra cond

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