𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Constructive characterizations for packing and covering with trees

✍ Scribed by András Frank; László Szegő

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
342 KB
Volume
131
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

We give a constructive characterization of undirected graphs which contain k spanning trees after adding any new edge. This is a generalization of a theorem of Henneberg and Laman who gave the characterization for k = 2. We also give a constructive characterization of graphs which have k edge-disjoint spanning trees after deleting any edge of them.

📜 SIMILAR VOLUMES

Packing and covering constants for certa
Packing and covering constants for certain families of trees. I
✍ A. Meir; J. W. Moon 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 518 KB

## Abstract If ℱ denotes a family of rooted trees, let __p~k~(n)__ and __c~k~(n)__ denote the average value of the __k__‐packing and __k__‐covering numbers of trees in ℱ that have __n__ nodes. We assume, among other things, that the generating function __y__ of trees in ℱ satisfies a relation of th

Packing and Covering Groups with Subgrou
Packing and Covering Groups with Subgroups
✍ D. Jungnickel; L. Storme 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 182 KB

We study the problem of covering or packing a finite group with subgroups of a specified order and obtain bounds on the size of such covers and packings. Our main results provide characterizations of the elementary abelian groups by the existence of large packings or small covers, respectively. Henc

Packing and Decomposition of Graphs with
Packing and Decomposition of Graphs with Trees
✍ Raphael Yuster 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 214 KB

Let H be a tree on h 2 vertices. It is shown that if n is sufficiently large and G=(V, E ) is an n-vertex graph with $(G) wnÂ2x , then there are w |E |Â(h&1)x edge-disjoint subgraphs of G which are isomorphic to H. In particular, if h&1 divides |E | then there is an H-decomposition of G. This result

Packing graphs with odd and even trees
Packing graphs with odd and even trees
✍ P. C. Fishburn 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 643 KB

The Gyarfas-Lehel tree-packing conjecture asserts that any sequence T,, T,, ..., Tn-l of trees with 1, 2, ..., n -1 edges packs into the complete graph K, on n vertices. The present paper examines two conjectures that jointly imply the Gydrfas-Lehel conjecture: 1. For n even, any TI, T 3 , . . ., T