共查询到20条相似文献,搜索用时 15 毫秒
1.
In this paper the conjecture on the kth upper multiexponent of primitive matrices proposed by R.A. Brualdi and Liu are completely proved. 相似文献
2.
M. Lewin and Y. Vitek conjecture [7] that every integer is an exponent of some n×n primitive matrix. In this paper, we prove three results related to Lewin and Vitek's conjecture: (1) Every integer is an exponent of some n×n primitive matrix. (2) The conjecture is true when n is sufficiently large. (3) We give a counterexample to show that the conjecture is not true in the case when n=11. 相似文献
3.
Hwa Kyung Kim 《Linear algebra and its applications》2010,433(1):72-98
For positive integers k and m, and a digraph D, the k-step m-competition graph of D has the same set of vertices as D and an edge between vertices x and y if and only if there are distinct m vertices v1,v2,…,vm in D such that there are directed walks of length k from x to vi and from y to vi for 1?i?m. In this paper, we present the definition of m-competition index for a primitive digraph. The m-competition index of a primitive digraph D is the smallest positive integer k such that is a complete graph. We study m-competition indices of primitive digraphs and provide an upper bound for the m-competition index of a primitive digraph. 相似文献
4.
ZHANGKEMIN BuYUEHUA 《高校应用数学学报(英文版)》1997,12(3):267-286
A locally semicomplete digraph is a digraph D=(V,A) satisfying the following condi-tion for every vertex x∈V the D[O(x)] and D[I(x)] are semicomplete digraphs. In this paper,we get some properties of cycles and determine the exponent set of primitive locally semicompleted digraphs. 相似文献
5.
6.
研究了围长为2的无限布尔方阵的本原性,通过无限有向图D(A)的直径给出了这类矩阵的本原指数的上确界,最后证明了直径小于等于d且围长为2的本原无限布尔方阵所构成的矩阵类的本原指数集为Ed^0={2,3,…,3d}. 相似文献
7.
8.
9.
Olivier Cogis 《Discrete Mathematics》1982,38(1):47-52
The Ferrers dimension of a digraph has been shown to be an extension of the order dimension. By proving a property of (finite) transitive Ferrers digraphs, we give an original proof of this above result and derive Ore's alternative definition of the order dimension. Still, the order dimension is proved to be ‘polynomially equivalent’ to the Ferrers dimension. 相似文献
10.
11.
Bolian Liu 《Linear and Multilinear Algebra》2013,61(1-4):131-138
If A is a primitive matrix, then there is a smallest power of A (its fully indecomposable exponent) which is fully indecomposable, and a smallest power of A (its strict fully indecomposable exponent) starting from which all powers are fully indecomposable. We obtain bounds on these two exponents for primitive Boolean matrices with symmetric one's. 相似文献
12.
Bolian Liu 《Linear and Multilinear Algebra》1992,31(1):131-138
If A is a primitive matrix, then there is a smallest power of A (its fully indecomposable exponent) which is fully indecomposable, and a smallest power of A (its strict fully indecomposable exponent) starting from which all powers are fully indecomposable. We obtain bounds on these two exponents for primitive Boolean matrices with symmetric one's. 相似文献
13.
Simone Severini 《Discrete Applied Mathematics》2006,154(12):1763-1765
We show that the adjacency matrix M of the line digraph of a d-regular digraph D on n vertices can be written as M=AB, where the matrix A is the Kronecker product of the all-ones matrix of dimension d with the identity matrix of dimension n and the matrix B is the direct sum of the adjacency matrices of the factors in a dicycle factorization of D. 相似文献
14.
S. Rao Kosaraju 《Journal of Graph Theory》1977,1(4):379-382
15.
Rudolf Müller 《Mathematical Programming》1996,73(1):31-49
We introduce the partial order polytope of a digraphD, defined as the convex hull of the incidence vectors of all transitive acyclic arc sets ofD. For this polytope we prove some classes of inequalities to be facet-defining and show that there is a polynomial separation algorithm for each of these classes. The results imply a polynomial separation algorithm for a class of valid inequalities of the clique partitioning polytope that includes the two-chorded odd cycle inequalities. The polyhedral results concerning the partial order polytope are of interest since a cutting plane based algorithm to solve the maximum weighted transitive acyclic subdigraph problem can be used to solve the maximum weighted acyclic subdigraph problem, the maximum weighted linear ordering problem and a flexible manufacturing problem. For the acyclic subdigraph polytope we show that the separation of simplet-reinforcedk-fence-inequalities is -complete. 相似文献
16.
17.
18.
19.
Let G be finite group and let S be a subset of G. We prove a necessary and sufficient condition for the Cayley digraph X(G, S) to be primitive when S contains the central elements of G. As an immediate consequence we obtain that a Cayley digraph X(G, S) on an Abelian group is primitive if and only if S−1S is a generating set for G. Moreover, it is shown that if a Cayley digraph X(G, S) on an Abelian group is primitive, then its exponent either is
or is not exceeding
. Finally, we also characterize those Cayley digraphs on Abelian groups with exponent
. In particular, we generalize a number of well-known results for the primitive circulant matrices. 相似文献