Abstract
In this dissertation, jointly with Prof. Wang, we prove five new results in graph theory. The first new result focuses on directed pentagons with given independent arcs. Let k and n be two positive integers with n ≥ 4k. Let D = (V, A) be a directed graph of order n. In 2019, Prof. Wang conjectured that if every vertex of D has degree at least (3n+2k−4)/2, then for any k independent arcs f1,...,fk of D and any integer partition n = n1 +···+nk with ni ≥ 4 for all 1 ≤ i ≤ k, D has k disjoint directed cycles C1,...,Ck of orders n1,...,nk, respectively such that fi is an arc of Ci for all 1 ≤ i ≤ k. In this dissertation, jointly with Prof. Wang, we verify the special case of n = 5k of this conjecture. If n = 5k and every vertex of D has degree at least (17k − 4)/2, then for any k independent arcs f1, f2, . . . , fk in D, there exist k disjoint directed cycles C1, C2, . . . , Ck of order 5 in D such that Ci contains fi for all i ∈ {1, 2, . . . , k}. Moreover, the degree condition is sharp.
Later, jointly with Prof. Wang, we prove three new results regarding packing problems. Let G be a bipartite graph with (X, Y) as its bipartition. We say G(X, Y) has a k-packing in a complete bipartite graph Bn(V1, V2) with X ⊆ V1 and Y ⊆ V2 if there exists a sequence of permutations on V(G), say Φ = (φ1,...,φk), such that φi(X) ⊆ V1, φi(Y) ⊆ V2 and E(φi(G)) ∩ E(φj(G)) = ∅ for all i,j ∈ {1,...,k} and i ≠ j. In this dissertation, we say a 2-packing of G(X, Y) in Bn(V1, V2) is a bipacking of G(X, Y) in Bn(V1, V2). We will show that if G is a bipartite graph of order n with girth at least 8, then there is a complete bipartite graph Bn+1 with order n + 1 such that there is a bipacking of G in Bn+1. The condition on the girth of G is sharp. This proves the conjecture proposed by Prof. Wang in 2019. Furthermore, we conjecture that for a bipartite graph G with order n and girth at least 4k where k ≥ 2, there is a k-packing of G in some Bn+k−1. We will also prove two weak versions of this conjecture in this dissertation. We show that for each tree T of order n = 2l with bipartite vertex sets of size k1 and k2, respectively, there is a k-packing of T in some complete bipartite graph Bn+m(X, Y), where m = h1 + h2 − k1 − k2 and h1h2 >2l2+(2k−4)l−k+1,h1 =|X| and h2 =|Y|. Moreover, we show that for each tree T of order n with bipartite vertex sets of size k1 and k2, respectively, there is a k-packing of T in some complete bipartite graph Bn+m(X, Y ), where m = h1 + h2 − k1 − k2 and h1h2−(k1+k2−1)(h1+h2)≥(n−1)(k−1), h1 =|X| and h2 =|Y|.
The last new result in this dissertation is regarding the embedding of bipartite graphs. A bipartite 2-regular graph is a bipartite graph G such that G = C2n1 ∪ C2n2 ∪ · · · ∪ C2nk with k ≥ 1, i.e., G is a vertex disjoint union of bipartite cycles. In this dissertation, jointly with Prof. Wang, we completely characterize the bipartite 2-regular graphs which can be uniquely bi-embedded into their bipartite complements. This work is an analogue of the result proved by Grzelec, Pilśniak, and Woźniak in 2024.