✦ LIBER ✦

On tree factorizations of Kn

✍ Scribed by Min-Li Yu

Publisher: John Wiley and Sons
Year: 1993
Tongue: English
Weight: 647 KB
Volume: 17
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190170608

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In this paper we exhibit a class of trees with the property that if T~k~ is a tree on k vertices that belongs to this class, then necessary and sufficient conditions for K~n~ to have a T~k~‐factorization are simply n = 0 (mod k) and n = 1 (mod 2(k ‐ 1)). (This class is large and in particular contains all caterpillars with an odd number of vertices.) As a corollary we obtain necessary and sufficient conditions for the existence of a K~1,k‐1~‐factorization of K~n~, which previously had only been known to be asymptotically sufficient. © 1993 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

Rainbow and orthogonal paths in factoriz

Rainbow and orthogonal paths in factorizations of Kn

✍ András Gyárfás; Mehdi Mhalla 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 164 KB

For n even, a factorization of a complete graph K n is a partition of the edges into n-1 perfect matchings, called the factors of the factorization. With respect to a factorization, a path is called rainbow if its edges are from distinct factors. A rainbow Hamiltonian path takes exactly one edge fro

On bipartite 2-factorizations of kn − I

On bipartite 2-factorizations of kn − I and the Oberwolfach problem

✍ Darryn Bryant; Peter Danziger 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 180 KB

It is shown that if F 1 , F 2 , ...,F t are bipartite 2-regular graphs of order n and 1 , 2 , . . . , t are positive integers such that 1 + 2 +• • •+ t = (n-2) / 2, 1 ≥ 3 is odd, and i is even for i = 2, 3, . . . , t, then there exists a 2-factorization of K n -I in which there are exactly i 2-facto

Tree-like Properties of Cycle Factorizat

Tree-like Properties of Cycle Factorizations

✍ Ian Goulden; Alexander Yong 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 125 KB

We provide a bijection between the set of factorizations, that is, ordered (n -1)tuples of transpositions in S n whose product is (12...n), and labelled trees on n vertices. We prove a refinement of a theorem of J. Dénes (1959, Publ. Math. Inst. Hungar. Acad. Sci. 4, 63-71) that establishes new tree

On the number of spanning trees of Kn an

On the number of spanning trees of Kn and Km, n

✍ Moh'd Z. Abu-Sbeih 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 170 KB

The object of this paper is to introduce a new technique for showing that the number of labelled spanning trees of the complete bipartite graph K,,,, is IT(m, n)l = m"-'n"-'. As an application, we use this technique to give a new proof of Cayley's formula IT(n)1 = nnm2, for the number of labelled s

Factors of trees

✍ Tao Wang 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 608 KB

Two criteria for a tree to have an f-factor and (g, f)-factors are presented, respectively. They simplify, respectively, Tutte's condition for a graph to havef-factors and Lov~sz's condition for a graph to have (g,f)-factors. An O(j V(T)/) algorithm and an O(l V(T)I') algorithm for f-factor and (g,

Edge-decompositions of Kn,n into isomorp

Edge-decompositions of Kn,n into isomorphic copies of a given tree

✍ Anna Lladó; S.C. López 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 167 KB

We study the Ha ¨ggkvist conjecture which states that, for each tree T with n edges, there is an edge-partition of the complete bipartite graph K n;n into n isomorphic copies of T . We use the concept of bigraceful labelings, introduced in [7], which give rise to cyclic decompositions of K n;n . Whe