Trails,Paths and Cycles of Digraphs with α2-stable Number 2
Let α2(D)=max{|X|:X ⊆ V(D)and D[X]has no 2-cycle} be theα2(D)-stable number of a digraph D.In[Proc.London Math.Soc.,42(1981)231-251],Thomassen constructed non-hamiltonian digraphs D with κ(D)=α(D)to show that the well-known Chvátal-Erdös theorem does not have obvious extension to di-graphs.Bang-Jensen and Thomassé conjectured that every digraph with arc strong-connectivity at least its stable number must have a spanning closed trail.The problem also remains unanswered whether a digraph with its arc strong-connectivity at least itsα2(D)-stable number has spanning trails or not.A digraph D is weakly trail-connected if for any two vertices x and y of D,D admits a spanning(x,y)-trail or a spanning(y,x)-trail,and is strongly trail-connected if for any two vertices x and y of D,D contains both a spanning(x,y)-trail and a spanning(y,x)-trail.We determine two well-characterized families of strong digraphs M and H,and prove each of the fol-lowing for any strong digraph D with α2(D)=2:(i)D is hamiltonian if and only if D ∉ M.(ii)D is weakly trail-connected.(iii)D is strongly trail-connected if and only if D ∉ H.In particular,every strong digraph D with α2(D)=2 has a hamiltonian path and every 2-strong digraph D with α2(D)=2 is strongly trail-connected.
NETL
NSTL
万方数据
