| dc.description.abstract | Graph decomposition is an important subject of graph theory since many
mathematical structures are linked to it and its result can be widely applied
in other fields. The factorization is a special type of graph decomposition,
and it has close connections to combinatorial designs. There are various decomposition
problems such as clique decomposition, star decomposition, path
decomposition, cycle decomposition, complete bipartite decomposition, and so
on. Nowadays, they continue to be popular topics of research.
In this thesis, the problems of antidirected cycle decomposition and directed
path decomposition of some digraph, and that of caterpillar factorization of
some graphs are investigated. There are various close connections between
graph decomposition and the arboricity of a graph. In this thesis, we also
show that the linear arboricity and the star arboricity of some graphs.
There are seven chapters in this thesis. In Chapter 1, some basic definitions
and notations are introduced. In Chapter 2, we first establish a necessary and
sufficient condition for the isomorphic path decomposition of complete tripari tite multigraphs. We then investigate the isomorphic directed path decomposition
of complete tripartite multidigraphs.
In Chapter 3, we give a necessary and sufficient condition for the existence
of the antidirected cycle decompositions of complete symmetric graphs. In
Chapter 4, we give a necessary and sufficient condition for the existence of
the antidirected cycle decompositions of complete symmetric graphs minus a
one-factor.
In Chapter 5, the caterpillar factorization of crowns are studied. We first
establish a necessary and sufficient condition for the balanced caterpillar factorization
of crowns. Then we give a necessary and sufficient condition for the
directed caterpillar factorization of symmetric crowns.
In Chapter 6, we first consider the problem of the star arboricity of crowns.
A lower bound is given. Then we investigate the star arboricity of some special
crowns. In Chapter 7, we consider the problem of the linear k-arboricity of
complete graph Kn for some specific k. | en_US |