Minimum tree decompositions with a given tree as a factor
MetadataShow full item record
A tree decomposition of a graph G is a family of subtrees whose sets of edges partition the set of edges of G. In this paper we are interested in the structure of the trees involved in tree decompositions with the minimum possible number of factors. We show that arbitrary trees may appear in minimum tree decompositions of maximal planar bipartite graphs, maximal planar graphs and regular graphs.
Is part ofThe Australasian Journal of Combinatorics, 2005, vol. 31, p. 47-59
European research projects
The following license files are associated with this item:
Showing items related by title, author, creator and subject.
Lladó, Anna; López Masip, Susana-Clara; Moragas, J. (Elsevier, 2010)Let T be a tree with m edges. A well-known conjecture of Ringel states that every tree T with m edges decomposes the complete graph K2m+1. Graham and H¨aggkvist conjectured that T also decomposes the complete bipartite ...
Hamidoune, Yahya Ould; Lladó, Anna; López Masip, Susana-Clara (Wiley, 2011)A d-regular graph is said to be superconnected if any disconnecting subset with cardinality at most d is formed by the neighbors of some vertex. A superconnected graph that remains connected after the failure of a vertex ...
Hamidoune, Yahya Ould; Lladó, Anna; López Masip, Susana-Clara (Springer, 2013)We investigate the structure of a digraph having a transitive automorphism group where every cutset of minimal cardinality consists of all successors or all predecessors of some vertex. We give a complete characterization ...