Extension Of The Strong Nine Dragon Tree Conjecture And The Nine Dragon Tree Theorem

A graph decomposition is to decompose a graph into edge-disjoint subgraphs.The arboricity of G is the minimum number of forests need to cover it.The fractional arboric-ity of G is definde ?f(G)=maxH(?)G,v(H)>1e(H)/V(H)-1.In 1986,Payan first introduced this concept.The famous Nash-Williams theorem presents a sufficient and necessary condi-tion for a graph G to be decomposed into at most k forests.In 1961,Nash-Williams and Tutte independently proposed and proved the necessary and sufficient condition for a graph G to contain k edge-disjoint spanning trees.In 2012,Montassier et al.proposed the famous Nine Dragon Tree Conjecture and Strong Nine Dragon Tree Conjecture.Cur-rently,the Nine Dragon Tree Conjecture was proven by Jiang and Yang in 2017.The Strong Nine Dragon Tree Conjecture has only been proved in some special cases:In 2013,Seog-Jin Kim et al.proved that the Strong Nine Dragon Tree Conjecture was cor-rect when k=1,and d=2.These results are a refined study on the forest decomposition of graphs.In 1993,Chen et al.proposed the concepts of i-forest and i-tree.In 2019,Fan et al.proposed the concept of i-arboricity of graph G:?i(G)is the minimum num-ber of i-forests need to cover it.They defined vi(G)=(min|P|>i)(e(G/P))/(|P|-i),proved that Nash-Williams theorem and Tutte theorem are equivalent to each other,and also proved that:Let G be an n-vertex graph.If vi(G)=k+?,0<??1,then G has k+1 edge-disjoint i-forests suth that k are i-trees,and the other has at least edges?(n-i),and this is sharp.The forest covering of graphs can be extended to independent sets covering of matroids.In 1965,Edmonds proved a necessary and sufficient condition for the elements in the matroid M to be partitioned into k independent sets.In 2019,Fan et al.proved that for a matroid M on E,if ?(M)=max ??X(?)E|X|/rM(X)=k+?k?N,0??<1,then E can be partitioned into k+1 independent sets with one of size at most ?·r(M).This thesis studies generalizations of the Nine Dragon Tree Theorem and the strong Nine Dragon Tree conjecture.First we extend the k=1,d=2 case of the Strong Nine Dragon Conjecture to i-forest and i-tree.Next we study a fractional version of the Nash-Williams Tutte theorem.Then we study independent set cover of lifted graphic matroid in signed graphs.This thesis consists of five chapters as follows:In Chapter 1,we first collect some basic notations that will be used frequently throughout the thesis.Then we present a survey of related work in the literature,and state the main results obtained in this thesis.In Chapter 2,we discuss the Strong Nine Dragon Tree Conjecture under the i-forest decomposition of the graph when k=1,and d=2.That is:when k=1,d=2,if that the graph G satisfies ?i(G)=maxH(?)G,|H|>ie(H)/|H|-i?1+1/2,then G decomposes into 2 i-forests,and one of the i-forests such that each connected component of it contains at most 2 edges.In Chapter 3,we prove that for a connected graph G,k is any non-negative integer,d is an integer satisfying 1?d<| V(G)|,if the graph G satisfies k+1??(G)=min|P|>1e(G/P)/|P|-1>k+d-1/d,then G contains k spanning trees and a forest,and this forest has at least one connected component whose edge number is greater than or equal to d.At the same time,we find a counterexamples to prove that the bounds given above is sharp.In Chapter 4,we study independent set cover of lifted graphic matroid.Assume G is a signed graph with only one of the cycles contained in it being an unbalanced cycle.E is the edge set of the connected signed graph G,M is a lifted graphic matroid on E.If ?(M)=max??X(?)Er|X|/rm(X)?1+d/d+2,then E can be partitioned into two independent sets B1 and I,and the number of degree of G[I]is at most d,G[I]is induced by I in G.In addition,we propose a conjecture that further generalizes this result and describe an idea of proving this conjecture and the problems encountered in pursuing this idea.In Chapter 5,we state some problems for further studies in the future.