Recently,scrambling index and competition index are widely applied to stochastic matrices and food webs. By analyzing the relationship of scrambling index and 2-competition index,n-「d/2」+ 1 was proved to be an upper...Recently,scrambling index and competition index are widely applied to stochastic matrices and food webs. By analyzing the relationship of scrambling index and 2-competition index,n-「d/2」+ 1 was proved to be an upper bound of the 2-competition2 index of a primitive digraph with exact d loops in this article.Moreover,the maximum index problem and the index set problem for the 2-competition index of primitive digraphs with minimally strong digraphs were settled.展开更多
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, ...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.展开更多
Let D = (V, E) be a primitive digraph. The exponent of D, denoted byγ(D), is the least integer k such that for any u, v∈ V there is a directed walk of length k from u to v. The local exponent of D at a vertex u∈ V,...Let D = (V, E) be a primitive digraph. The exponent of D, denoted byγ(D), is the least integer k such that for any u, v∈ V there is a directed walk of length k from u to v. The local exponent of D at a vertex u∈ V, denoted by exp_D (u), is the least integer k such that there is a directed walk of length k from u to v for each v ε V. Let V = {1,2,….,n}. Following [1], the vertices of V are ordered so that exp_D (1) ≤exp_D (2) ≤…≤exp_D(n) =λ(D). Let E_n(i):= {exp_D (i) ∈D PD_n}, where PD_n is the set of all primitive digraphs of order n. It is known that E_n(n) = {γ(D) D∈PD_n} has been completely settled by [7]. In 1998, E_n(1) was characterized by [5]. In this paper, the authors describe E_n(2) for all n≥2.展开更多
For any positive integers k and m, the k-step m-competition graph C^（D） of a digraph D has the same set of vertices as D and there is an edge between vertices x and y if and only if there are distinct m vertices vi,...For any positive integers k and m, the k-step m-competition graph C^（D） of a digraph D has the same set of vertices as D and there is an edge between vertices x and y if and only if there are distinct m vertices vi, v2, .., Vm in D such that there are directed walks of length k from x to vi and from y to vi for all 1 ≤ i≤ m. The m-competition index of a primitive digraph D is the smallest positive integer k such that Ckm（D） is a complete graph. In this paper, we obtained some sharp upper bounds for the m-competition indices of various classes of primitive digraphs.展开更多
Let D = （V, E） be a primitive digraph. The vertex exponent of D at a vertex v∈ V, denoted by expD（v）, is the least integer p such that there is a v →u walk of length p for each u ∈ V. Following Brualdi and Liu,...Let D = （V, E） be a primitive digraph. The vertex exponent of D at a vertex v∈ V, denoted by expD（v）, is the least integer p such that there is a v →u walk of length p for each u ∈ V. Following Brualdi and Liu, we order the vertices of D so that exPD（V1） ≤ exPD（V2） …≤ exPD（Vn）. Then exPD（Vk） is called the k- point exponent of D and is denoted by exPD （k）, 1≤ k ≤ n. In this paper we define e（n, k） ：= max{expD （k） ｜ D ∈ PD（n, 2）} and E（n, k） ：= {exPD（k）｜ D ∈ PD（n, 2）}, where PD（n, 2） is the set of all primitive digraphs of order n with girth 2. We completely determine e（n, k） and E（n, k） for all n, k with n ≥ 3 and 1 ≤ k ≤ n.展开更多
Let A be an n×n primitive Boolean matrix. γ(A) is the least number k such that A k=J. σ(A) is the number of 1 entry in A . In this paper, we consider the parameter M ′(k,n)= min {σ...Let A be an n×n primitive Boolean matrix. γ(A) is the least number k such that A k=J. σ(A) is the number of 1 entry in A . In this paper, we consider the parameter M ′(k,n)= min {σ(A)|A k=J, trace (A)=0} and obtain the values of M ′(2,n) and M ′(k,n) for k≥2n-6 . Furthermore, the characterization of solution of A 2=J with trace (A) =0 and σ(A)=3n-3 is completely determined.展开更多
基金National Natural Science Foundations of China(No.11272100,No.50865001)
文摘Recently,scrambling index and competition index are widely applied to stochastic matrices and food webs. By analyzing the relationship of scrambling index and 2-competition index,n-「d/2」+ 1 was proved to be an upper bound of the 2-competition2 index of a primitive digraph with exact d loops in this article.Moreover,the maximum index problem and the index set problem for the 2-competition index of primitive digraphs with minimally strong digraphs were settled.
文摘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.
基金National Natural Science Foundation of China Jiangsu Provincial Natural Science Foundation of China.
文摘Let D = (V, E) be a primitive digraph. The exponent of D, denoted byγ(D), is the least integer k such that for any u, v∈ V there is a directed walk of length k from u to v. The local exponent of D at a vertex u∈ V, denoted by exp_D (u), is the least integer k such that there is a directed walk of length k from u to v for each v ε V. Let V = {1,2,….,n}. Following [1], the vertices of V are ordered so that exp_D (1) ≤exp_D (2) ≤…≤exp_D(n) =λ(D). Let E_n(i):= {exp_D (i) ∈D PD_n}, where PD_n is the set of all primitive digraphs of order n. It is known that E_n(n) = {γ(D) D∈PD_n} has been completely settled by [7]. In 1998, E_n(1) was characterized by [5]. In this paper, the authors describe E_n(2) for all n≥2.
基金Supported by the National Natural Science Foundation of China(No.11571123,11671156)the Guangdong Provincial Natural Science Foundation(Grant No.2015A030313377)
文摘For any positive integers k and m, the k-step m-competition graph C^（D） of a digraph D has the same set of vertices as D and there is an edge between vertices x and y if and only if there are distinct m vertices vi, v2, .., Vm in D such that there are directed walks of length k from x to vi and from y to vi for all 1 ≤ i≤ m. The m-competition index of a primitive digraph D is the smallest positive integer k such that Ckm（D） is a complete graph. In this paper, we obtained some sharp upper bounds for the m-competition indices of various classes of primitive digraphs.
基金Supported by the National Natural Science Foundation of China(No.10771061,No.10771058)SRF of Hunan Provincial Education Department(No.07C267).
文摘Let D = （V, E） be a primitive digraph. The vertex exponent of D at a vertex v∈ V, denoted by expD（v）, is the least integer p such that there is a v →u walk of length p for each u ∈ V. Following Brualdi and Liu, we order the vertices of D so that exPD（V1） ≤ exPD（V2） …≤ exPD（Vn）. Then exPD（Vk） is called the k- point exponent of D and is denoted by exPD （k）, 1≤ k ≤ n. In this paper we define e（n, k） ：= max{expD （k） ｜ D ∈ PD（n, 2）} and E（n, k） ：= {exPD（k）｜ D ∈ PD（n, 2）}, where PD（n, 2） is the set of all primitive digraphs of order n with girth 2. We completely determine e（n, k） and E（n, k） for all n, k with n ≥ 3 and 1 ≤ k ≤ n.
文摘Let A be an n×n primitive Boolean matrix. γ(A) is the least number k such that A k=J. σ(A) is the number of 1 entry in A . In this paper, we consider the parameter M ′(k,n)= min {σ(A)|A k=J, trace (A)=0} and obtain the values of M ′(2,n) and M ′(k,n) for k≥2n-6 . Furthermore, the characterization of solution of A 2=J with trace (A) =0 and σ(A)=3n-3 is completely determined.
