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.     

Generalized characteristic polynomials of graph bundles

In this paper, we find computational formulae for generalized characteristic polynomials of graph bundles. We show that the number of spanning trees in a graph is the partial derivative (at (0,1)) of the generalized characteristic polynomial of the graph. Since the reciprocal of the Bartholdi zeta function of a graph can be derived from the generalized characteristic polynomial of a graph, consequently, the Bartholdi zeta function of a graph bundle can be computed by using our computational formulae.     

Zeta functions of line, middle, total graphs of a graph and their coverings

We consider the (Ihara) zeta functions of line graphs, middle graphs and total graphs of a regular graph and their (regular or irregular) covering graphs. Let L(G), M(G) and T(G) denote the line, middle and total graph of G, respectively. We show that the line, middle and total graph of a (regular and irregular, respectively) covering of a graph G is a (regular and irregular, respectively) covering of L(G), M(G) and T(G), respectively. For a regular graph G, we express the zeta functions of the line, middle and total graph of any (regular or irregular) covering of G in terms of the characteristic polynomial of the covering. Also, the complexities of the line, middle and total graph of any (regular or irregular) covering of G are computed. Furthermore, we discuss the L-functions of the line, middle and total graph of a regular graph G.     

The eccentric connectivity index of nanotubes and nanotori

Let G be a molecular graph. The eccentric connectivity index ξ^c(G) is defined as ξ^c(G)=∑_u∈V(G)deg_G(u)ε_G(u), where deg_G(u) denotes the degree of vertex u and ε_G(u) is the largest distance between u and any other vertex v of G. In this paper exact formulas for the eccentric connectivity index of TUC₄C₈(S) nanotube and TC₄C₈(S) nanotorus are given.     

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.     

Enlargements of filtrations and path decompositions at non stopping times

Azéma associated with an honest time L the supermartingale and established some of its important properties. This supermartingale plays a central role in the general theory of stochastic processes and in particular in the theory of progressive enlargements of filtrations. In this paper, we shall give an additive characterization for these supermartingales, which in turn will naturally provide many examples of enlargements of filtrations. We combine this characterization with some arguments from both initial and progressive enlargements of filtrations to establish some path decomposition results, closely related to or reminiscent of Williams' path decomposition results. In particular, some of the fragments of the paths in our decompositions end or start with a new family of random times which are not stopping times, nor honest times.     

A generalized characteristic polynomial of a graph having a semifree action

For an abelian group Γ, a formula to compute the characteristic polynomial of a Γ-graph has been obtained by Lee and Kim [Characteristic polynomials of graphs having a semi-free action, Linear algebra Appl. 307 (2005) 35-46]. As a continuation of this work, we give a computational formula for generalized characteristic polynomial of a Γ-graph when Γ is a finite group. Moreover, after showing that the reciprocal of the Bartholdi zeta function of a graph can be derived from the generalized characteristic polynomial of a graph, we compute the reciprocals of the Bartholdi zeta functions of wheels and complete bipartite graphs as an application of our formula.     

Coefficients of ergodicity and the scrambling index

For a primitive stochastic matrix S, upper bounds on the second largest modulus of an eigenvalue of S are very important, because they determine the asymptotic rate of convergence of the sequence of powers of the corresponding matrix. In this paper, we introduce the definition of the scrambling index for a primitive digraph. 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). We investigate the scrambling index for primitive digraphs, and give an upper bound on the scrambling index of a primitive digraph in terms of the order and the girth of the digraph. By doing so we provide an attainable upper bound on the second largest modulus of eigenvalues of a primitive matrix that make use of the scrambling index.     

Minimum rank problems

A graph describes the zero-nonzero pattern of a family of matrices, with the type of graph (undirected or directed, simple or allowing loops) determining what type of matrices (symmetric or not necessarily symmetric, diagonal entries free or constrained) are described by the graph. The minimum rank problem of the graph is to determine the minimum among the ranks of the matrices in this family; the determination of maximum nullity is equivalent. This problem has been solved for simple trees [P.M. Nylen, Minimum-rank matrices with prescribed graph, Linear Algebra Appl. 248 (1996) 303-316, C.R. Johnson, A. Leal Duarte, The maximum multiplicity of an eigenvalue in a matrix whose graph is a tree, Linear and Multilinear Algebra 46 (1999) 139-144], trees allowing loops [L.M. DeAlba, T.L. Hardy, I.R. Hentzel, L. Hogben, A. Wangsness. Minimum rank and maximum eigenvalue multiplicity of symmetric tree sign patterns, Linear Algebra Appl. 418 (2006) 389-415], and directed trees allowing loops [F. Barioli, S. Fallat, D. Hershkowitz, H.T. Hall, L. Hogben, H. van der Holst, B. Shader, On the minimum rank of not necessarily symmetric matrices: a preliminary study, Electron. J. Linear Algebra 18 (2000) 126-145]. We survey these results from a unified perspective and solve the minimum rank problem for simple directed trees.     

New upper bounds for Estrada index of bipartite graphs

Suppose G is a graph and λ₁,λ₂,…,λ_n are the eigenvalues of G. The Estrada index EE(G) of G is defined as the sum of e^λ_i, 1≤i≤n. In this paper some new upper bounds for the Estrada index of bipartite graphs are presented. We apply our result on a (4,6)-fullerene to improve our bound given in an earlier paper.     

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.     

Transitive parabolic unitals in semifield planes

Every semifield plane with spread in PG(3,K), where K is a field admitting a quadratic extension K⁺, is shown to admit a transitive parabolic unital. The author gratefully acknowledges helpful comments of the referee in the writing of this article.     

Pattern Avoidance in Alternating Sign Matrices

We generalize the definition of a pattern from permutations to alternating sign matrices. The number of alternating sign matrices avoiding 132 is proved to be counted by the large Schr?der numbers, 1, 2, 6, 22, 90, 394, .... We give a bijection between 132-avoiding alternating sign matrices and Schr?der paths, which gives a refined enumeration. We also show that the 132-, 123-avoiding alternating sign matrices are counted by every second Fibonacci number. Received January 2, 2007     

On the null-spaces of acyclic and unicyclic singular graphs

For acyclic and unicyclic graphs we determine a necessary and sufficient condition for a graph G to be singular. Further, it is shown that this characterization can be used to construct a basis for the null-space of G.     

Set maps, umbral calculus, and the chromatic polynomial

Some important properties of the chromatic polynomial also hold for any polynomial set map satisfying

     

Sign patterns that require almost unique rank

A sign pattern matrix is a matrix whose entries are from the set {+,-,0}. For a real matrix B, sgn(B) is the sign pattern matrix obtained by replacing each positive (respectively, negative, zero) entry of B by + (respectively, −, 0). For a sign pattern matrix A, the sign pattern class of A, denoted Q(A), is defined as {B:sgn(B)=A}. The minimum rank mr(A) (maximum rank MR(A)) of a sign pattern matrix A is the minimum (maximum) of the ranks of the real matrices in Q(A). Several results concerning sign patterns A that require almost unique rank, that is to say, the sign patterns A such that MR(A) = mr(A) + 1, are established and are extended to sign patterns A for which the spread is d=MR(A)-mr(A). A complete characterization of the sign patterns that require almost unique rank is obtained.     

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.     

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.     

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 Z-eigenvalues of the adjacency tensors for uniform hypergraphs

The adjacency matrices for graphs are generalized to the adjacency tensors for uniform hypergraphs, and some fundamental properties for the adjacency tensor and its Z-eigenvalues of a uniform hypergraph are obtained. In particular, some bounds on the smallest and the largest Z-eigenvalues of the adjacency tensors for uniform hypergraphs are presented.