✦ LIBER ✦

Trees with 1-factors and oriented trees

✍ Scribed by Rodica Simion

Publisher: Elsevier Science
Year: 1991
Tongue: English
Weight: 632 KB
Volume: 88
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(91)90061-6

No coin nor oath required. For personal study only.

✦ Synopsis

Simion, R., Trees with l-factors and oriented trees, Discrete Mathematics 88 (1991) 93-104.

In this paper we present some results on trees with a l-factor: generating functions and asymptotics for the number of such trees, labeled, rooted, planted and unlabeled. We show that almost all trees with a l-factor have nontrivial automorphism groups. We also exhibit constructive correspondences between trees with a l-factor and oriented trees, which lead to asymptotics for the number of self-converse oriented trees.

📜 SIMILAR VOLUMES

Ramsey-type results for oriented trees

✍ Kohayakawa, Yoshiharu; ?uczak, Tomasz; R�dl, Vojt?ch 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 486 KB

For a graph G and a digraph h, w e write Gfi (respectively, G 5 2) if every orientation (respectively, acyclic orientation) of the edges of G results in an induced copy of k In this note w e study how small the graphs G such that Gor such that G 5 i/ may be, if k is a given oriented tree ? on n vert

The number of trees with a 1-factor

✍ J.W. Moon 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 608 KB

The asymptotic behaviour of the number of trees with a 1-factor is determined for various families of trees

Trees with very few eigenvalues

✍ Robert A. Beezer 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 381 KB

## Abstract The number of distinct eigenvalues of the adjacency matrix of a graph is bounded below by the diameter of the graph plus one. Many graphs that achieve this lower bound exhibit much symmetry, for example, distance‐transitive and distance‐regular graphs. Here we provide a recursive constr

Spanning trees with many leaves

✍ Guoli Ding; Thor Johnson; Paul Seymour 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 95 KB

## Abstract We show that if __G__ is a simple connected graph with and $|V(G)| \,\neq\,t+2$, then __G__ has a spanning tree with > __t__ leaves, and this is best possible. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 189–197, 2001

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

✍ 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