Premium
Decompositions of graphs into trees
Author(s) -
Lonc Zbigniew
Publication year - 1989
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190130403
Subject(s) - combinatorics , mathematics , conjecture , graph , partition (number theory) , vertex (graph theory) , discrete mathematics
Let θ be a family of graphs. By a θ‐decomposition of a graph G we mean a partition λ of the edge set of G such that every F ϵ π spans in G a subgraph isomorphic to a graph in θ. In this paper we state the following conjecture: If T 1 and T 2 are two trees having relatively prime sizes then there exists c = c(T 1 T 2 ) such that every graph G satisfying the condition δ(G) ⩾ c has a { T 1 , T 2 }‐decom‐position. We prove this conjecture for some special pairs of trees. In particular, we prove it in the following cases: (i) T 1 and T 2 are stars having relatively prime sizes; (ii) T 1 and T 2 are paths having relatively prime sizes; and. (iii) T 1 = T 2 ‐ {v}, where v is a terminal vertex in T 2 .