具有给定指数的本原有向图的Hamilton性质 (英文)

Hamilton Property of Primitive Digraph with Given Exponent

英文关键词:primitive digraph  exponent  Hamiltonian  girth  Frobenius number.

中文摘要:

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

英文摘要:

      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 exponent n+s(n-2). Then D is Hamiltonian. (2) Suppose that D is a primitive digraph on n vertices which contains a loop, and γ(D)=2n-2. Then D is Hamiltonian if and only if max{d(u,v)|γ(u,v)=2n-2}=n-2.