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.     

Some properties of graphs determined by edge zeta functions

In 1989, Hashimoto introduced an edge zeta function of a finite graph, which is a generalization of the Ihara zeta function. The edge zeta function is the reciprocal of a polynomial in twice as many indeterminants as edges in the graph and can be computed via a determinant expression. We look at graph properties which we can determine using the edge zeta function. In particular, the edge zeta function is enough to deduce the clique number, the number of Hamiltonian cycles, and whether a graph is perfect or chordal. Finally, we present a new example illustrating that the Ihara zeta function cannot necessarily do the same.     

An iterative construction of isospectral digraphs

Recently, Storm used generating functions to provide a proof that an infinite family of graphs constructed by Cooper have the same Ihara zeta function. Here, we generalize the construction of that infinite family of graphs to a directed graph construction. A similar generating function proof technique applies, and we exhibit conditions under which our digraphs have the same spectra with respect to the adjacency matrix.     

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 Ihara zeta function of the complement of a semiregular bipartite graph

We study the Ihara zeta function of the complement of a semiregular bipartite graph. A factorization formula for the Ihara zeta function is derived via which the number of spanning trees is computed. For a class of complements of semiregular bipartite graphs, it is shown that they have the same Ihara zeta function if and only if they are cospectral.     

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.     

On digraphs with no two disjoint directed cycles

We obtain a result on configurations in 2-connected digraphs with no two disjoint dicycles. We derive various consequences, for example a short proof of the characterization of the minimal digraphs having no vertex meeting all dicycles and a polynomially bounded algorithm for finding a dicycle through any pair of prescribed arcs in a digraph with no two disjoint dicycles, a problem which is NP-complete for digraphs in general.     

Multiplicativity of acyclic local tournaments

A homomorphism of a digraph to another digraph is an edge-preserving vertex mapping. A digraphH is said to be multiplicative if the set of digraphs which do not admit a homomorphism toH is closed under categorical product. In this paper we discuss the multiplicativity of acyclic Hamiltonian digraphs, i.e., acyclic digraphs which contains a Hamiltonian path. As a consequence, we give a complete characterization of acyclic local tournaments with respect to multiplicativity.     

The spectra of Manhattan street networks

The multidimensional Manhattan street networks constitute a family of digraphs with many interesting properties, such as vertex symmetry (in fact they are Cayley digraphs), easy routing, Hamiltonicity, and modular structure. From the known structural properties of these digraphs, we determine their spectra, which always contain the spectra of hypercubes. In particular, in the standard (two-dimensional) case it is shown that their line digraph structure imposes the presence of the zero eigenvalue with a large multiplicity.     

Ihara's zeta function for periodic graphs and its approximation in the amenable case

In this paper, we give a more direct proof of the results by Clair and Mokhtari-Sharghi [B. Clair, S. Mokhtari-Sharghi, Zeta functions of discrete groups acting on trees, J. Algebra 237 (2001) 591-620] on the zeta functions of periodic graphs. In particular, using appropriate operator-algebraic techniques, we establish a determinant formula in this context and examine its consequences for the Ihara zeta function. Moreover, we answer in the affirmative one of the questions raised in [R.I. Grigorchuk, A. ?uk, The Ihara zeta function of infinite graphs, the KNS spectral measure and integrable maps, in: V.A. Kaimanovich, et al. (Eds.), Proc. Workshop, Random Walks and Geometry, Vienna, 2001, de Gruyter, Berlin, 2004, pp. 141-180] by Grigorchuk and ?uk. Accordingly, we show that the zeta function of a periodic graph with an amenable group action is the limit of the zeta functions of a suitable sequence of finite subgraphs.     

Zeta functions of finite graphs and coverings, III

A graph theoretical analog of Brauer-Siegel theory for zeta functions of number fields is developed using the theory of Artin L-functions for Galois coverings of graphs from parts I and II. In the process, we discuss possible versions of the Riemann hypothesis for the Ihara zeta function of an irregular graph.     

Posets with interval upper bound graphs

Competition graphs of transitive acyclic digraphs are strict upper bound graphs. This paper characterizes those posets, which can be considered transitive acyclic digraphs, which have upper bound graphs that are interval graphs. The results proved here may shed some light on the open question of those digraphs which have interval competition graphs.This material is taken from Chapter 3 of my (maiden name Diny) PhD Dissertation.     

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.     

On the connectivity of randomm-orientable graphs and digraphs

We consider graphs and digraphs obtained by randomly generating a prescribed number of arcs incident at each vertex. We analyse their almost certain connectivity and apply these results to the expected value of random minimum length spanning trees and arborescences. We also examine the relationship between our results and certain results of Erdős and Rényi.     

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.     

On the Ihara Zeta Function of Cones Over Regular Graphs

In this paper we derive a formula of the Ihara zeta function of a cone over a regular graph that involves the spectrum of the adjacency matrix of the cone. We show that the Ihara zeta function and the spectrum of the adjacency matrix of the cone determine each other and we characterize those cones that satisfy the graph theory Riemann hypothesis.     

A note on the girth of digraphs

Behzad, Chartrand and Wall conjectured that the girth of a diregular graph of ordern and outdegreer is not greater than [n /r]. This conjecture has been proved forr=2 by Behzad and forr=3 by Bermond. We prove that a digraph of ordern and halfdegree ≧4 has girth not exceeding [n / 4]. We also obtain short proofs of the above results. Our method is an application of the theory of connectivity of digraphs.     

Connected graphs containing a given connected graph as a unique greatest common subgraph

Those connected graphsG are determined for which there exist nonisomorphic connected graphs of equal size containingG as a unique greatest common subgraph. Analogous results are also obtained for weakly connected and strongly connected digraphs, as well as for induced subgraphs and induced subdigraphs.This research was supported by a Western Michigan University faculty research fellowship.This research was supported in part by a Western Michigan University research assistantship from the Graduate College and the College of Arts and Sciences.     

A note on zeta functions of Ihara type for normal Kähler graphs

A regular Kähler graph is a compound of two regular graphs. When adjacency operators of component graphs are commutative, we introduce equivalence relations on sets of primitive bicolored paths, which are considered as sets of trajectory-segments of magnetic fields on this Kähler graph, we study their zeta functions of Ihara type, and show a correspondence to those for ordinary regular graphs.     

Renormalization of multiple zeta values

Multiple zeta values (MZVs) in the usual sense are the special values of multiple variable zeta functions at positive integers. Their extensive studies are important in both mathematics and physics with broad connections and applications. In contrast, very little is known about the special values of multiple zeta functions at non-positive integers since the values are usually undefined. We define and study multiple zeta functions at integer values by adapting methods of renormalization from quantum field theory, and following the Hopf algebra approach of Connes and Kreimer. This definition of renormalized MZVs agrees with the convergent MZVs and extends the work of Ihara–Kaneko–Zagier on renormalization of MZVs with positive arguments. We further show that the important quasi-shuffle (stuffle) relation for usual MZVs remains true for the renormalized MZVs.