Noncommuting graphs of matrices over semirings

We study diameters and girths of noncommuting graphs of semirings. For a noncommutative semiring that is either multiplicatively or additively cancellative, we find the diameter and the girth of its noncommuting graph and prove that it is Hamiltonian. Moreover, we find diameters and girths of noncommuting graphs of all nilpotent matrices over a semiring, all invertible matrices over a semiring, all noninvertible matrices over a semiring, and the full matrix semiring. In nearly all cases we prove that diameters are less than or equal to 2 and girths are less than or equal to 3, except in the case of 2×2 nilpotent matrices.     

Bijective linear rank preservers for spaces of matrices over antinegative semirings

We classify the bijective linear operators on spaces of matrices over antinegative commutative semirings with no zero divisors which preserve certain rank functions such as the symmetric rank, the factor rank and the tropical rank. We also classify the bijective linear operators on spaces of matrices over the max-plus semiring which preserve the Gondran-Minoux row rank or the Gondran-Minoux column rank.     

On the diameters of commuting graphs

The commuting graph of a ring R, denoted by Γ(R), is a graph whose vertices are all non-central elements of R and two distinct vertices x and y are adjacent if and only if xy = yx. Let D be a division ring and n ? 3. In this paper we investigate the diameters of Γ(M_n(D)) and determine the diameters of some induced subgraphs of Γ(M_n(D)), such as the induced subgraphs on the set of all non-scalar non-invertible, nilpotent, idempotent, and involution matrices in M_n(D). For every field F, it is shown that if Γ(M_n(F)) is a connected graph, then diam Γ(M_n(F)) ? 6. We conjecture that if Γ(M_n(F)) is a connected graph, then diam Γ(M_n(F)) ? 5. We show that if F is an algebraically closed field or n is a prime number and Γ(M_n(F)) is a connected graph, then diam Γ(M_n(F)) = 4. Finally, we present some applications to the structure of pairs of idempotents which may prove of independent interest.     

Invertible and nilpotent matrices over antirings

In this paper, we characterize invertible matrices over an arbitrary commutative antiring S with 1 and find the structure of GL_n(S). We find the number of nilpotent matrices over an entire commutative finite antiring. We prove that every nilpotent n×n matrix over an entire antiring can be written as a sum of ⌈log₂n⌉ square-zero matrices and also find the necessary number of square-zero summands for an arbitrary trace-zero matrix to be expressible as their sum.     

Inequalities for Gondran-Minoux rank and idempotent semirings

The rank-sum, rank-product, and rank-union inequalities for Gondran-Minoux rank of matrices over idempotent semirings are considered. We prove these inequalities for matrices over quasi-selective semirings without zero divisors, which include matrices over the max-plus semiring. Moreover, it is shown that the inequalities provide the linear algebraic characterization for the class of quasi-selective semirings. Namely, it is proven that the inequalities hold for matrices over an idempotent semiring S without zero divisors if and only if S is quasi-selective. For any idempotent semiring which is not quasi-selective it is shown that the rank-sum, rank-product, and rank-union inequalities do not hold in general. Also, we provide an example of a selective semiring with zero divisors such that the rank-sum, rank-product, and rank-union inequalities do not hold in general.     

On unimodular graphs

We study graphs whose adjacency matrices have determinant equal to 1 or −1, and characterize certain subclasses of these graphs. Graphs whose adjacency matrices are totally unimodular are also characterized. For bipartite graphs having a unique perfect matching, we provide a formula for the inverse of the corresponding adjacency matrix, and address the problem of when that inverse is diagonally similar to a nonnegative matrix. Special attention is paid to the case that such a graph is unicyclic.     

Fixed zeros in the model matching problem for systems over semirings

This paper studies “fixed zeros” of solutions to the model matching problem for systems over semirings. Such systems have been used to model queueing systems, communication networks, and manufacturing systems. The main contribution of this paper is the discovery of two fixed zero structures, which possess a connection with the extended zero semimodules of solutions to the model matching problem. Intuitively, the fixed zeros provides an essential component that is obtained from the solutions to the model matching problem. For discrete event dynamic systems modeled in max-plus algebra, a common Petri net component constructed from the solutions to the model matching problem can be discovered from the fixed zero structure.     

Completion of operator partial matrices associated with chordal graphs

H. Dym and I. Gohberg established in [6] necessary and sufficient conditions for the existence and uniqueness of an invertible block matrix F=(F_ij)_i,j=1,...,n such that F_ij=R_ij for |i–j|m and F^–1 has a band triangular factorization and so (F^–1)_ij=0 for |i–j|>m. Here R_ij, |i–j|m are given block matrices.The aim of this paper is to generalize these results in two directions. First, we shall allow R_ij to be an (linear bounded) operator acting between the Hilbert spaces H_j and H_i. Secondly, the set of indices of the given R_ij will be more general than banded ones. In fact, we will consider index sets which have an associated graph which is chordal. The case of partial positive operator matrices is also discussed.     

Determinant identities for Laplace matrices

We show that every minor of an n×n Laplace matrix, i.e., a symmetric matrix whose row- and column sums are 0, can be written in terms of those minors that are obtained by deleting two rows and the corresponding columns. The proof is based on a classical determinant identity due to Sylvester. Furthermore, we show how our result can be applied in the context of electrical networks and spanning tree enumeration.     

On directed zero-divisor graphs of finite rings

For an artinian ring R, the directed zero-divisor graph Γ(R) is connected if and only if there is no proper one-sided identity element in R. Sinks and sources are characterized and clarified for a finite ring R. Especially, it is proved that for any ring R, if there exists a source y in Γ(R) with y²=0, then |R|=4 and R={0,x,y,z}, where x and z are left identity elements and yx=0=yz. Such a ring R is also the only ring such that Γ(R) has exactly one source. This shows that Γ(R) cannot be a network for any finite or infinite ring R.     

Nowhere-zero eigenvectors of graphs

A vector is called nowhere-zero if it has no zero entry. In this article we search for graphs with nowhere-zero eigenvectors. We prove that distance-regular graphs and vertex-transitive graphs have nowhere-zero eigenvectors for all of their eigenvalues and edge-transitive graphs have nowhere-zero eigenvectors for all non-zero eigenvalues. Among other results, it is shown that a graph with three distinct eigenvalues has a nowhere-zero eigenvector for its smallest eigenvalue.     

Strongly self-dual graphs

We present a class of graphs whose adjacency matrices are nonsingular with integral inverses, denoted h-graphs. If the h-graphs G and H with adjacency matrices M(G) and M(H) satisfy M(G)^-1=SM(H)S, where S is a signature matrix, we refer to H as the dual of G. The dual is a type of graph inverse. If the h-graph G is isomorphic to its dual via a particular isomorphism, we refer to G as strongly self-dual. We investigate the structural and spectral properties of strongly self-dual graphs, with a particular emphasis on identifying when such a graph has 1 as an eigenvalue.     

Energy of line graphs

The energy of a graph is equal to the sum of the absolute values of its eigenvalues. The energy of a matrix is equal to the sum of its singular values. We establish relations between the energy of the line graph of a graph G and the energies associated with the Laplacian and signless Laplacian matrices of G.     

Characteristic polynomial of a generalized complete product of matrices

For a simple graph G, let denote the complement of G relative to the complete graph and let P_G(x)=det(xI-A(G)) where A(G) denotes the adjacency matrix of G. The complete product G∇H of two simple graphs G and H is the graph obtained from G and H by joining every vertex of G to every vertex of H. In [2]P_G∇H(x) is represented in terms of P_G, , P_H and . In this paper we extend the notion of complete product of simple graphs to that of generalized complete product of matrices and obtain their characteristic polynomials.     

Constructably Laplacian integral graphs

A graph is Laplacian integral if the spectrum of its Laplacian matrix consists entirely of integers. We consider the class of constructably Laplacian integral graphs - those graphs that be constructed from an empty graph by adding a sequence of edges in such a way that each time a new edge is added, the resulting graph is Laplacian integral. We characterize the constructably Laplacian integral graphs in terms of certain forbidden vertex-induced subgraphs, and consider the number of nonisomorphic Laplacian integral graphs that can be constructed by adding a suitable edge to a constructably Laplacian integral graph. We also discuss the eigenvalues of constructably Laplacian integral graphs, and identify families of isospectral nonisomorphic graphs within the class.     

On Hadamard diagonalizable graphs

Of interest here is a characterization of the undirected graphs G such that the Laplacian matrix associated with G can be diagonalized by some Hadamard matrix. Many interesting and fundamental properties are presented for such graphs along with a partial characterization of the cographs that have this property.     

The weighted complexity and the determinant functions of graphs

The complexity of a graph can be obtained as a derivative of a variation of the zeta function [S. Northshield, A note on the zeta function of a graph, J. Combin. Theory Ser. B 74 (1998) 408-410] or a partial derivative of its generalized characteristic polynomial evaluated at a point [D. Kim, H.K. Kim, J. Lee, Generalized characteristic polynomials of graph bundles, Linear Algebra Appl. 429 (4) (2008) 688-697]. A similar result for the weighted complexity of weighted graphs was found using a determinant function [H. Mizuno, I. Sato, On the weighted complexity of a regular covering of a graph, J. Combin. Theory Ser. B 89 (2003) 17-26]. In this paper, we consider the determinant function of two variables and discover a condition that the weighted complexity of a weighted graph is a partial derivative of the determinant function evaluated at a point. Consequently, we simply obtain the previous results and disclose a new formula for the complexity from a variation of the Bartholdi zeta function. We also consider a new weighted complexity, for which the weights of spanning trees are taken as the sum of weights of edges in the tree, and find a similar formula for this new weighted complexity. As an application, we compute the weighted complexities of the product of the complete graphs.     

The energy change of weighted graphs

The energy of an (edge)-weighted graph is the sum of the absolute values of the eigenvalues of its (weighted) adjacency matrix. We study how the energy of a weighted graph changes when the weights change. We give some sufficient conditions so that the energy of a weighted graph increases when the positive weight increases. We also characterize some classes of weighted graphs satisfying these sufficient conditions.     

The Laplacian spread of quasi-tree graphs

The Laplacian spread of a graph is defined to be the difference between the largest eigenvalue and the second-smallest eigenvalue of the Laplacian matrix of the graph. Bao, Tan and Fan [Y.H. Bao, Y.Y. Tan,Y.Z. Fan, The Laplacian spread of unicyclic graphs, Appl. Math. Lett. 22 (2009) 1011-1015.] characterize the unique unicyclic graph with maximum Laplacian spread among all connected unicyclic graphs of fixed order. In this paper, we characterize the unique quasi-tree graph with maximum Laplacian spread among all quasi-tree graphs in the set Q(n,d) with .     

The Laplacian incidence energy of graphs

The Laplacian incidence energy of a graph is defined as the sum of the singular values of its normalized oriented incidence matrix. In this paper, we give sharp upper and lower bounds as well as the Coulson integral formula for the Laplacian incidence energy. Moreover, we show a close relation of the Laplacian incidence energy, normalized incidence energy and Randi? energy.