Cycle Extendability And Vertex-disjoint Cycles In Digraphs

Given an integer c≥2,a c-partite extended tournament D is an orientation of a c-partite complete graph such that if(x,y)∈A(D),where x ∈Vi and y ∈ Vj,then there is an arc from every vertex in Vi to every vertex in Vj,where V1,…,Vc are partite sets of D.A cycle C is weakly extendable if there exists a cycle C’ such that V(C)(?) V(C’)and |V(C’)|≤|V(C)|+2.D is said to be weakly cycle extendable if D is not acyclic and every non-Hamiltonian cycle C of D is weakly extendable.Further,we call D fully weakly cycle extendable if it is weakly cycle extendable and for every v∈ V(D),there is a cycle of length 3 through v.This thesis obtains the following results.Result 1.Let D be a c-partite extended tournament with c>4.Then D is weakly cycle extendable only and only if D has a Hamiltonian cycle.A digraph D is a zigzag digraph if V(D)-V1∪…∪Vc,where |V(D)|≥5,c≥4 and A(V2,V1)=A(Vi,V2)=A(V1,Vi)=Φ for any i∈{3,4,…,c} and |V1|=|V2|=|V3|+…+|Vc|.Result 2.Let D be a,c-partite extended tournament with c≥ 4.If D has a Hamiltonian cycle and is neither a zigzag tournament nor a.4-partite tournament with at least five vertices,then D is fully weakly cycle extendable.For a vertex v of a digraph D,we denote by dD+(v)and dD-(v)the out-degree and in-degree of v in D,respectively.For two distinct vertices u and v in D,the arc from u to v is defined as uv.A 1-factor F of a digraph D is a spanning subgraph such that dF+(v)=dF-(v)=1 for any vertex v∈ V(D).In other words,a 1-factor of a digraph D is a spanning subgraph in which every component is a cycle.This thesis obtains the following result.Result 3.Let k be a positive integer and let D be a digraph of order n.,where n≥9k-1.If dD+(u)+dD-(v)≥n for every pair of vertices u and v with uv(?)A(D),then D has a 1-factor with exactly k cycles.