Premium
Tree decomposition of graphs
Author(s) -
Yuster Raphael
Publication year - 1998
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199805)12:3<237::aid-rsa2>3.0.co;2-w
Subject(s) - combinatorics , mathematics , tree (set theory) , decomposition , graph , struct , spanning tree , discrete mathematics , chemistry , computer science , organic chemistry , programming language
Let H be a tree on h ≥2 vertices. It is shown that if G =( V , E ) is a graph with \delta (G)\ge (|V|/2)+10h^4\sqrt{|V|\log|V|} , and h −1 divides | E |, then there is a decomposition of the edges of G into copies of H . This result is asymptotically the best possible for all trees with at least three vertices. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12, 237–251, 1998