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.
Balanced decomposition and factorization are
special types of graph decomposition,
and they have close connections to combinatorial designs.
Balanced decompositions of complete multigraphs and
factorizations of complete multigraphs correspond to
blanced imcomplete block designs (BIBD) and
resolvable designs, respectively.
Nowadays, they continue to be popular topics of research.
There are various decomposition problems such as
clique decomposition, star decomposition,
path decomposition, cycle decomposition,
complete bipartite decomposition, and so on.
In theis thesis, the problems of balanced star decomposition and
balanced path decomposition of some graphs,
and that of directed star factorization and
directed path factorization of some digraphs are investigated.
There are six chapters in this thesis.
In Chapter 1, some basic definitions and notation are introduced.
In Chapter 2,
the balanced star decompositions of graphs are investigated.
We first give a criterion for the balanced star decompositions of
regular multiple graphs.
We then give a necessary and sufficient condition
for the existence of the balanced star decompositions of
complete bipartite multigraphs which are not regular
if the partite sets have different size.
In Chapter 3, the path decomposition of graphs are studied.
We first establish a necessary and sufficient condition
for the balanced path decomposition of
complete bipartite multigraph.
We then give a criterion for the path decomposition of
complete tripartite graph.
In Chapter 4,
we find some decomposition invariants of crown, which include
the path number, linear arboricity and star arboricity.
In Chapter 5,
we first consider the problems of directed star factorizations and
directed path factorizations of the symmetric crown,
the necessary and sufficient conditions are given.
We then study directed star factorization of the symmetric
complete mutipartite digraph and give some sufficient conditions.
In Chapter 6,
we consider the problem of decomposing
the symmetric complete bipartite digraph into distars,
some sufficient conditions are given. | en_US |