Paper Info
Title
Edge-decomposition of Graphs into Copies of a Tree with Four Edges.
Abstract
We study edge-decompositions of highly connected graphs into copies of a given tree. In particular we attack the following conjecture by Barat and Thomassen: for each tree T, there exists a natural number k(T) such that if C; is a k(T)-edge-connected graph, and vertical bar E(T)vertical bar divides vertical bar E(G)vertical bar, then E(G) has a decomposition into copies of T. As one of our main results it is sufficient to prove the conjecture for bipartite graphs. The same result has been independently obtained by Carsten Thomassen (2013). Let Y be the unique tree with degree sequence (1, 1, 1, 2, 3). We prove that if is a 191-edge-connected graph of size divisible by 1, then G has a Y-decomposition. This is the first instance of such a theorem, in which the tree is different from a path or a star. Recently Carsten Thomassen proved a more general decomposition theorem for bistars, which yields the same result with a worse constant.
Year
Venue
Keywords
2014
ELECTRONIC JOURNAL OF COMBINATORICS
graph theory,decomposition,tree,edge-connectivity
Field
DocType
Volume
Graph theory,Discrete mathematics,Graph,Combinatorics,Existential quantification,Bipartite graph,Decomposition theorem,Degree (graph theory),Conjecture,Mathematics
Journal
21.0
Issue
ISSN
Citations 
1.0
1077-8926
10
PageRank 
References 
Authors
1.01
3
2
Name
Order
Citations
PageRank
János Barát114114.18
Dániel Gerbner24621.61