Rainbow Structure In Tournament Graph System

There are occasions that a undirected graph is not the appropriate structure to model a particular situation.For example,the roads between locations are all one-way streets,which leads to the definition of a directed graph.Given a vertex set V,let G1,…,Gm be m graphs defined on vertex set V,for different i,j,1≤i ≤j≤m,Gi can be as same as Gj.We call g={G1,…,Gm} is a graph system.A graph system G={G1,…,Gm} with V as vertex set,if for each i ∈[m]such that E(H)?∪i∈[m]E(Gi)and |E(H)∩E(Gi)|≤1,then the graph H is said to be rainbow.We say that a graph H with vertices in V is a partial G-transversal if there exists an injectionφ:E(H)→[m]such that e ∈ E(Gφ(e))for each e ∈ E(H).If in addition |E(H)|=m,then H is a G-transversal(and φ a bijection).A tournament is a orientation of the complete graph,and Rédei[1]demonstrated that every tournament contains a directed Hamiltonian path and gave a stronger result that every tournament has odd-numbered directed Hamiltonian paths.Moon[2]gave the theorem that "Every nontrivial strong tournament is vertex-pancyclic".Joos and Kim[3]gave the rainbow version of Dirac’s theorem "Let n ∈N and n ≥ 3.Suppose g={G1,…,Gn} is a collection of not necessarily distinct n vertex graphs with the same vertex set such that δ(Gi)≥ n/2 for each i∈[n].Then there exists a Hamiltonian G-transversal".According to the generalization of Dirac’s theorem in graph system by Joos and Kim,we generalize some of the conclusions from the tournament to the tournament graph system.We obtain the following main results:(1)Let τ be a tournament graph system consisting of any n-1 transitive tournaments defined on the vertex set V={v1,…,vn},then τ has a τ-transversal tree.(2)Let τ be a tournament graph system consisting of n-1 random tournaments defined on the vertex set V={v1,…,vn}.When n→∞,the probability P of having a τ-transversal path in τ approaches 1.(3)Let T be a tournament graph system consisting of any n strong tournaments defined on the vertex set V=｛v1,…,vn)},where n≥ 4.For any vertex Vi∈E V,T has a directed rainbow triangle including vi.(4)Let T be a tournament graph system consisting of any n+2 strong tournaments defined on the vertex set V={v1,…,vn},when n≥3 and n is an odd number,T is directed rainbow vertex-pancyclic;Let T be a tournament graph system consisting of any n+1 strong tournaments defined on the vertex set V={v1,…,vn},when n≥4 and n is an even number,T is directed rainbow vertex-pancyclic.