具有给定指数的本原有向图的Hamilton性质

本文解决了１９８２年Ｊ．Ａ．Ｒｏｓｓ提出的两个问题，并得到如下结果：（１）设Ｄ是具有围长ｓ＞１和指数γ（Ｄ）＝ｎ＋ｓ（ｎ－２）的ｎ阶本原有向图，则Ｄ是Ｈａｍｉｌｔｏｎ的；（２）设Ｄ是含有环的ｎ阶本原有向图且γ（Ｄ）＝２ｎ－２，则Ｄ是Ｈａｍｉｌｔｏｎ的当且仅当ｍａｘ｛ｄ（ｕ,ｖ）|γ（ｕ，ｖ）＝２ｎ－２｝＝ｎ－２．

Hamilton Property of Primitive Digraph with Given Exponent

Let D be a digraph. We call D primitive if there exists a positive integer ksuch that for all ordered pairs of venices u, v V(D) (not necessarily distinct), there isa directed walk of length k from u to v. In 1982, J.A.Ross posed two problems: (1) If Dis a primitive digraph on n vertices with girth s>1 and (D) = n s(n-2), does Dcontain an elementary circuit of length n? (2) Let D be a strong digraph on n verticeswhich contains a loop and suppose D is not isomorphic to Bi,n for i=1, 2, n-1(see Figure 1), if (D) =2n-2, does D contain an elementary circuit of length n?In this paper, we have solved both completely and obtained the following results: (1)Suppose that D is a primitive digraph on n vertices with girth s>1 and exponentn s (n-2). Then D is Hamiltonian. (2) Suppose that D is a primitive digraph on nvertices which contains a loop, and (D)=2n-2. Then D is Hamiltonian if and only if max {d(u,v))=(u, v)= 2}=2} =n-2.