Eigenvalues and colorings of digraphs

Wilf’s eigenvalue upper bound on the chromatic number is extended to the setting of digraphs. The proof uses a generalization of Brooks’ Theorem to digraph colorings.     

Unitary matrix digraphs and minimum semidefinite rank

For an undirected simple graph G, the minimum rank among all positive semidefinite matrices with graph G is called the minimum semidefinite rank (msr) of G. In this paper, we show that the msr of a given graph may be determined from the msr of a related bipartite graph. Finding the msr of a given bipartite graph is then shown to be equivalent to determining which digraphs encode the zero/nonzero pattern of a unitary matrix. We provide an algorithm to construct unitary matrices with a certain pattern, and use previous results to give a lower bound for the msr of certain bipartite graphs.     

Lower bounds for the energy of digraphs

The energy of a digraph D is defined as , where z₁,…,z_n are the eigenvalues of D. In this article we find lower bounds for the energy of digraphs in terms of the number of closed walks of length 2, extending in this way the result obtained by Caporossi et al. [G. Caporossi, D. Cvetkovi?, I. Gutman, P. Hansen, Variable neighborhood search for extremal graphs. 2. Finding graphs with extremal energy, J. Chem. Inf. Comput. Sci. 39 (1999) 984-996]: for all graphs G with m edges. Also, we study digraphs with three eigenvalues.     

Bartholdi zeta and L-functions of weighted digraphs, their coverings and products

Since a zeta function of a regular graph was introduced by Ihara [Y. Ihara, On discrete subgroups of the two by two projective linear group over p-adic fields, J. Math. Soc. Japan 19 (1966) 219-235], many kinds of zeta functions and L-functions of a graph or a digraph have been defined and investigated. Most of the works concerning zeta and L-functions of a graph contain the following: (1) defining a zeta function, (2) defining an L-function associated with a (regular) graph covering, (3) providing their determinant expressions, and (4) computing the zeta function of a graph covering and obtaining its decomposition formula as a product of L-functions. As a continuation of those works, we introduce a zeta function of a weighted digraph and an L-function associated with a weighted digraph bundle. A graph bundle is a notion containing a cartesian product of graphs and a (regular or irregular) graph covering. Also we provide determinant expressions of the zeta function and the L-function. Moreover, we compute the zeta function of a weighted digraph bundle and obtain its decomposition formula as a product of the L-functions.     

Exponents of 2-coloring of symmetric digraphs

A 2-coloring (G₁,G₂) of a digraph is 2-primitive if there exist nonnegative integers h and k with h+k>0 such that for each ordered pair (u,v) of vertices there exists an (h,k)-walk in (G₁,G₂) from u to v. The exponent of (G₁,G₂) is the minimum value of h+k taken over all such h and k. In this paper, we consider 2-colorings of strongly connected symmetric digraphs with loops, establish necessary and sufficient conditions for these to be 2-primitive and determine an upper bound on their exponents. We also characterize the 2-colored digraphs that attain the upper bound and the exponent set for this family of digraphs on n vertices.     

Extreme values of the stationary distribution of random walks on directed graphs

We examine the stationary distribution of random walks on directed graphs. In particular, we focus on the principal ratio, which is the ratio of maximum to minimum values of vertices in the stationary distribution. We give an upper bound for this ratio over all strongly connected graphs on n vertices. We characterize all graphs achieving the upper bound and we give explicit constructions for these extremal graphs. Additionally, we show that under certain conditions, the principal ratio is tightly bounded. We also provide counterexamples to show the principal ratio cannot be tightly bounded under weaker conditions.     

On the primitivity of Cayley digraphs

We give a necessary and sufficient group theoretic condition for a Cayley digraph to be primitive.     

Hoffman polynomials of nonnegative irreducible matrices and strongly connected digraphs

For a nonnegative n × n matrix A, we find that there is a polynomial f(x)∈R[x] such that f(A) is a positive matrix of rank one if and only if A is irreducible. Furthermore, we show that the lowest degree such polynomial f(x) with tr f(A) = n is unique. Thus, generalizing the well-known definition of the Hoffman polynomial of a strongly connected regular digraph, for any irreducible nonnegative n × n matrix A, we are led to define its Hoffman polynomial to be the polynomial f(x) of minimum degree satisfying that f(A) is positive and has rank 1 and trace n. The Hoffman polynomial of a strongly connected digraph is defined to be the Hoffman polynomial of its adjacency matrix. We collect in this paper some basic results and open problems related to the concept of Hoffman polynomials.     

Primitive digraphs with smallest large exponent

A primitive digraph D on n vertices has large exponent if its exponent, γ(D), satisfies α_n?γ(D)?w_n, where α_n=⌊w_n/2⌋+2 and w_n=(n-1)²+1. It is shown that the minimum number of arcs in a primitive digraph D on n?5 vertices with exponent equal to α_n is either n+1 or n+2. Explicit constructions are given for fixed n even and odd, for a primitive digraph on n vertices with exponent α_n and n+2 arcs. These constructions extend to digraphs with some exponents between α_n and w_n. A necessary and sufficient condition is presented for the existence of a primitive digraph on n vertices with exponent α_n and n+1 arcs. Together with some number theoretic results, this gives an algorithm that determines for fixed n whether the minimum number of arcs is n+1 or n+2.     

Primitive digraphs with the largest scrambling index

The scrambling index of a primitive digraph D is the smallest positive integer k such that for every pair of vertices u and v, there is a vertex w such that we can get to w from u and v in D by directed walks of length k; it is denoted by k(D). In [M. Akelbek, S. Kirkland, Coefficients of ergodicity and the scrambling index, preprint] we gave the upper bound on k(D) in terms of the order and the girth of a primitive digraph D. In this paper, we characterize all the primitive digraphs such that the scrambling index is equal to the upper bound.     

Multipartite Moore digraphs

We derive some Moore-like bounds for multipartite digraphs, which extend those of bipartite digraphs, under the assumption that every vertex of a given partite set is adjacent to the same number δ of vertices in each of the other independent sets. We determine when a multipartite Moore digraph is weakly distance-regular. Within this framework, some necessary conditions for the existence of a r-partite Moore digraph with interpartite outdegree δ > 1 and diameter k = 2m are obtained. In the case δ = 1, which corresponds to almost Moore digraphs, a necessary condition in terms of the permutation cycle structure is derived. Additionally, we present some constructions of dense multipartite digraphs of diameter two that are vertex-transitive.     

Primitive non-powerful symmetric loop-free signed digraphs with given base and minimum number of arcs

In [B.M. Kim, B.C. Song, W. Hwang, Primitive graphs with given exponents and minimum number of edges, Linear Algebra Appl. 420 (2007) 648-662], the minimum number of edges of a simple graph on n vertices with exponent k was determined. In this paper, we completely determine the minimum number, H(n,k), of arcs of primitive non-powerful symmetric loop-free signed digraphs on n vertices with base k, characterize the underlying digraphs which have H(n,k) arcs when k is 2, nearly characterize the case when k is 3 and propose an open problem.     

Ihara zeta functions of digraphs

After defining and exploring some of the properties of Ihara zeta functions of digraphs, we improve upon Kotani and Sunada’s bounds on the poles of Ihara zeta functions of undirected graphs by considering digraphs whose adjacency matrices are directed edge matrices.     

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.     

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.     

Distance spectral radius of trees with fixed number of pendent vertices

The distance spectral radius ρ(G)$\rho (G)$ of a graph G   is the largest eigenvalue of the distance matrix D(G)$D(G)$. In this paper, we characterize the graph with minimum distance spectral radius among trees with fixed number of pendent vertices.     

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 .     

On the nullity of graphs with pendant trees

The nullity of a graph is defined as the multiplicity of the eigenvalue zero in the spectrum of the adjacency matrix of the graph. We investigate a class of graphs with pendant trees, and express the nullity of such graph in terms of that of its subgraphs. As an application of our results, we characterize unicyclic graphs with a given nullity.     

The Laplacian spectral radius of some bipartite graphs

In this paper, we study the largest Laplacian spectral radius of the bipartite graphs with n vertices and k cut edges and the bicyclic bipartite graphs, respectively. Identifying the center of a star K_1,k and one vertex of degree n of K_m,n, we denote by the resulting graph. We show that the graph (1?k?n-4) is the unique graph with the largest Laplacian spectral radius among the bipartite graphs with n vertices and k cut edges, and (n?7) is the unique graph with the largest Laplacian spectral radius among all the bicyclic bipartite graphs.