Disjoint Cycles In Tournament And Line Graphs

The tournament and the line graph are two kinds of classical graphs,and it is a very important issue to study disjoint cycle for tournament and line graph.In this paper,we first study the disjoint cycle in the tournament.The Bermond-Thomassen conjecture states that,for any positive integer r,a digraph of minimum out-degree at least 2r-1 contains at least r vertex-disjoint directed cycles.In 2014,the conjecture was proved for tournaments by Bessy,Bang-Jensen and Thomasse.Recently,Lichiardopol improved this result by showing that a 2r-1-regular tournament containing at least 7/6r-7/3 disjoint cycles and proved that a tournament with minimum semi-degree grater than or equal to(q-1)r-1 contains at least r vertex-disjoint q-cycles,where integer q>3 and r ≥ 1.At the same time,he conjectured that a tournament T with δ+(T)≥(q-1)r-1 contains at least r vertex-disjoint q-cycles,where integer q>3 and r ≥ 1.In this paper,we extend Lichiardopol’s result to tournaments with semi-degree at least 2r-1 and prove the conjecture is true when r = 2.Secondly,we also study the edge-disjoint Hamilton cycles and the Hamiltonian of the line graph.The Hamiltonian problem is a classical problem in graph theory,but it is known that the existence problem of the Hamiltonian circle is an NP-complete problem.For an integer s ≥ 0,a graph G is s-hamiltonian if for any vertex subset S(?)V(G)with |S| ≤s,G-S is hamiltonian.In this note,we show that if G is a planar simple graph and L(G)is 4-connected,then L(G)is hamiltonian-connected and 2-hamiltonian.These results generalize work of Lai in[Every 4-connected line graph of a planar graph is hamiltonian,Graph and Combinatorics 10(1994)249-253].The Bermond conjecture states that,if G is a Hamilton decomposable graph,then L(G),the line graph of G,is Hamilton decomposable.In this paper,we give a partial result of this conjecture.As we all know that a spanning closed trail of a graph guarantees a Hamilton cycle in its line graph.Recently,Hao Li et al proved that if a graph G with minimum degree at least 4k has k edge-disjoint spanning closed trails,then L(G)contains k edge-disjoint Hamilton cycles.In this note,we show that if a graph G with minimum degree at least 4k has k edge-disjoint Hamilton cycles,then L(G)contains at least 2k edge-disjoint Hamilton cycles.