On the generalized indices of boolean matrices

We characterize completely those Boolean matrices with the largest generalized indices in the class of Boolean matrices and in the class of reducible Boolean matrices and derive a new upper bound for the generalized index in terms of period. We also generalize the upper and lower multiexponents of primitive Boolean matrices to general Boolean matrices.     

Generalized Indices of Boolean Matrices

We obtain upper bounds for generalized indices of matrices in the class of nearly reducible Boolean matrices and in the class of critically reducible Boolean matrices, and prove that these bounds are the best possible.     

Computing tight upper bounds on the algebraic connectivity of certain graphs

A generalized Bethe tree is a rooted unweighted tree in which vertices at the same level have the same degree. Let B be a generalized Bethe tree. The algebraic connectivity of:

the generalized Bethe tree B,

a tree obtained from the union of B and a tree T isomorphic to a subtree of B such that the root vertex of T is the root vertex of B,

a tree obtained from the union of r generalized Bethe trees joined at their respective root vertices,

a graph obtained from the cycle C_r by attaching B, by its root, to each vertex of the cycle, and

a tree obtained from the path P_r by attaching B, by its root, to each vertex of the path,

is the smallest eigenvalue of a special type of symmetric tridiagonal matrices. In this paper, we first derive a procedure to compute a tight upper bound on the smallest eigenvalue of this special type of matrices. Finally, we apply the procedure to obtain a tight upper bound on the algebraic connectivity of the above mentioned graphs.

     

A bound on the generalized competition index of a primitive matrix using Boolean rank

For a positive integer m where 1?m?n, the m-competition index (generalized competition index) of a primitive digraph is the smallest positive integer k such that for every pair of vertices x and y, there exist m distinct vertices v₁,v₂,…,v_m such that there are directed walks of length k from x to v_i and from y to v_i for 1?i?m. The m-competition index is a generalization of the scrambling index and the exponent of a primitive digraph. In this study, we determine an upper bound on the m-competition index of a primitive digraph using Boolean rank and give examples of primitive Boolean matrices that attain the bound.     

Sharp bounds on the spectral radius of a nonnegative matrix

We give upper and lower bounds for the spectral radius of a nonnegative matrix using its row sums and characterize the equality cases if the matrix is irreducible. Then we apply these bounds to various matrices associated with a graph, including the adjacency matrix, the signless Laplacian matrix, the distance matrix, the distance signless Laplacian matrix, and the reciprocal distance matrix. Some known results in the literature are generalized and improved.     

Orthogonal representations over finite fields and the chromatic number of graphs

We study the relationship between the minimum dimension of an orthogonal representation of a graph over a finite field and the chromatic number of its complement. It turns out that for some classes of matrices defined by a graph the 3-colorability problem is equivalent to deciding whether the class defined by the graph contains a matrix of rank 3 or not. This implies the NP-hardness of determining the minimum rank of a matrix in such a class. Finally we give for any class of matrices defined by a graph that is interesting in this respect a reduction of the 3-colorability problem to the problem of deciding whether or not this class contains a matrix of rank equal to three.The author is financially supported by the Cooperation Centre Tilburg and Eindhoven Universities.     

Extremal graph characterization from the upper bound of the Laplacian spectral radius of weighted graphs

We consider weighted graphs, where the edge weights are positive definite matrices. In this paper, we obtain two upper bounds on the spectral radius of the Laplacian matrix of weighted graphs and characterize graphs for which the bounds are attained. Moreover, we show that some known upper bounds on the Laplacian spectral radius of weighted and unweighted graphs can be deduced from our upper bounds.     

围长为2的本原无限布尔方阵类的本原指数集

研究了围长为2的无限布尔方阵的本原性,通过无限有向图D（A）的直径给出了这类矩阵的本原指数的上确界,最后证明了直径小于等于d且围长为2的本原无限布尔方阵所构成的矩阵类的本原指数集为Ed^0={2,3,…,3d}．     

具有确定非零对角元个数的布尔矩阵广义幂敛指数的极矩阵

设A是周期为P的n阶布尔矩阵,1≤i≤n,A的广义幂敛指数k(A,i)是使得Ak和Ak+p有i行对应相等的最小非负整数k.本文刻画了恰含d(1≤d≤n)个非零对角元的n阶布尔矩阵的广义幂敛指数的极矩阵.     

On the hall exponents of boolean matrices

We obtain upper bounds on the Hall exponents of symmetric and microsymmetric primitive Boolean matrices respectively.