Graphs whose critical groups have larger rank

The critical group C(G) of a graph G is a refinement of the number of spanning trees of the graph and is closely connected with the Laplacian matrix. Let r(G) be the minimum number of generators (i.e., the rank) of the group C(G) and β(G) be the number of independent cycles of G. In this paper, some forbidden induced subgraphs are given for r(G) = n − 3 and all graphs with r(G) = β(G) = n − 3 are characterized.     

Critical groups for homeomorphism classes of graphs

In this paper the weighted fundamental circuits intersection matrix of an edge-labeled graph is introduced for computing the critical groups for homeomorphism classes of graphs. As an application, it is proved that for any given finite connected simple graph there is a homeomorphic graph with cyclic critical group.     

Sandpile groups and the coeulerian property for random directed graphs

We consider random directed graphs, and calculate the distribution of the cokernels of their laplacian, following the methods used by Wood. As a corollary, we show that the probability that a random digraph is coeulerian is asymptotically upper bounded by a constant around 0.43.     

Critical groups for complete multipartite graphs and Cartesian products of complete graphs

The critical group of a connected graph is a finite abelian group, whose order is the number of spanning trees in the graph, and which is closely related to the graph Laplacian. Its group structure has been determined for relatively few classes of graphs, e.g., complete graphs and complete bipartite graphs. For complete multipartite graphs , we describe the critical group structure completely. For Cartesian products of complete graphs , we generalize results of H. Bai on the k-dimensional cube, by bounding the number of invariant factors in the critical group, and describing completely its p-primary structure for all primes p that divide none of . © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 231–250, 2003     

Digraphs with at most one trivial critical ideal

Critical ideals generalize the critical group, Smith group and the characteristic polynomials of the adjacency and Laplacian matrices of a graph. We give a complete characterization of the digraphs with at most one trivial critical ideal. Which implies the characterizations of the digraphs whose critical group has one invariant factor equal to one, and the digraphs whose Smith group has one invariant factor equal to one.     

Eigenvalue interlacing and weight parameters of graphs

Eigenvalue interlacing is a versatile technique for deriving results in algebraic combinatorics. In particular, it has been successfully used for proving a number of results about the relation between the (adjacency matrix or Laplacian) spectrum of a graph and some of its properties. For instance, some characterizations of regular partitions, and bounds for some parameters, such as the independence and chromatic numbers, the diameter, the bandwidth, etc., have been obtained. For each parameter of a graph involving the cardinality of some vertex sets, we can define its corresponding weight parameter by giving some “weights” (that is, the entries of the positive eigenvector) to the vertices and replacing cardinalities by square norms. The key point is that such weights “regularize” the graph, and hence allow us to define a kind of regular partition, called “pseudo-regular,” intended for general graphs. Here we show how to use interlacing for proving results about some weight parameters and pseudo-regular partitions of a graph. For instance, generalizing a well-known result of Lovász, it is shown that the weight Shannon capacity Θ^* of a connected graph Γ, with n vertices and (adjacency matrix) eigenvalues λ₁ > λ₂ … λ_n, satisfies

where Θ is the (standard) Shannon capacity and v is the positive eigenvector normalized to have smallest entry 1. In the special case of regular graphs, the results obtained have some interesting corollaries, such as an upper bound for some of the multiplicities of the eigenvalues of a distance-regular graph. Finally, some results involving the Laplacian spectrum are derived.     

Deza graphs: A generalization of strongly regular graph

We consider the following generalization of strongly regular graphs. A graph G is a Deza graph if it is regular and the number of common neighbors of two distinct vertices takes on one of two values (not necessarily depending on the adjacency of the two vertices). We introduce several ways to construct Deza graphs, and develop some basic theory. We also list all diameter two Deza graphs which are not strongly regular and have at most 13 vertices.     

A note on unimodular congruence of the Laplacian matrix of a graph

Let G be a simple connected graph and L(G) be its Laplacian matrix. In this note, we prove that L(G) is congruent by a unimodular matrix to its Smith normal form if and only if G is a tree.     

The critical group of <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">m</Emphasis></Subscript> × <Emphasis Type="Italic">C</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>

In this paper, the structure of the critical group of the graph K _m × C _n is determined, where m, n ≥ 3.     

New families of strongly regular graphs

We apply symmetric balanced generalized weighing matrices with zero diagonal to construct four parametrically new infinite families of strongly regular graphs. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 208–217, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10038     

Lifting constructions of strongly regular Cayley graphs

We give two “lifting” constructions of strongly regular Cayley graphs. In the first construction we “lift” a cyclotomic strongly regular graph by using a subdifference set of the Singer difference sets. The second construction uses quadratic forms over finite fields and it is a common generalization of the construction of the affine polar graphs [7] and a construction of strongly regular Cayley graphs given in [15]. The two constructions are related in the following way: the second construction can be viewed as a recursive construction, and the strongly regular Cayley graphs obtained from the first construction can serve as starters for the second construction. We also obtain association schemes from the second construction.     

Differential Posets and Smith Normal Forms

We conjecture a strong property for the up and down maps U and D in an r-differential poset: DU + tI and UD + tI have Smith normal forms over . In particular, this would determine the integral structure of the maps U, D, UD, DU, including their ranks in any characteristic. As evidence, we prove the conjecture for the Young-Fibonacci lattice Y F studied by Okada and its r-differential generalizations Z(r), as well as verifying many of its consequences for Young’s lattice Y and the r-differential Cartesian products Y ^r .     

The Laplacian spectral radius of graphs on surfaces

Let G be an n-vertex (n?3) simple graph embeddable on a surface of Euler genus γ (the number of crosscaps plus twice the number of handles). Denote by Δ the maximum degree of G. In this paper, we first present two upper bounds on the Laplacian spectral radius of G as follows:

(i)

     

Smith meets Smith: Smith normal form of Smith matrix

In 1861, Henry John Stephen Smith [H.J.S. Smith, On systems of linear indeterminate equations and congruences, Philos. Trans. Royal Soc. London. 151 (1861), pp. 293–326] published famous results concerning solving systems of linear equations. The research on Smith normal form and its applications started and continues. In 1876, Smith [H.J.S. Smith, On the value of a certain arithmetical determinant, Proc. London Math. Soc. 7 (1875/76), pp. 208–212] calculated the determinant of the n?×?n matrix ((i,?j)), having the greatest common divisor (GCD) of i and j as its ij entry. Since that, many results concerning the determinants and related topics of GCD matrices, LCM matrices, meet matrices and join matrices have been published in the literature. In this article these two important research branches developed by Smith, in 1861 and in 1876, meet for the first time. The main purpose of this article is to determine the Smith normal form of the Smith matrix ((i,?j)). We do this: we determine the Smith normal form of GCD matrices defined on factor closed sets.     

Generalized frieze pattern determinants and higher angulations of polygons

Frieze patterns (in the sense of Conway and Coxeter) are in close connection to triangulations of polygons. Broline, Crowe and Isaacs have assigned a symmetric matrix to each polygon triangulation and computed the determinant. In this paper we consider d-angulations of polygons and generalize the combinatorial algorithm for computing the entries in the associated symmetric matrices; we compute their determinants and the Smith normal forms. It turns out that both are independent of the particular d  -angulation, the determinant is a power of d−1$d-1$, and the elementary divisors only take values d−1$d-1$ and 1. We also show that in the generalized frieze patterns obtained in our setting every adjacent 2×2$2\times 2$-determinant is 0 or 1, and we give a combinatorial criterion for when they are 1, which in the case d=3$d=3$ gives back the Conway–Coxeter condition on frieze patterns.     

Asymptotic spectral analysis of growing regular graphs

We propose the quantum probabilistic techniques to obtain the asymptotic spectral distribution of the adjacency matrix of a growing regular graph. We prove the quantum central limit theorem for the adjacency matrix of a growing regular graph in the vacuum and deformed vacuum states. The condition for the growth is described in terms of simple statistics arising from the stratification of the graph. The asymptotic spectral distribution of the adjacency matrix is obtained from the classical reduction.

     

Sandpile groups and spanning trees of directed line graphs

We generalize a theorem of Knuth relating the oriented spanning trees of a directed graph G and its directed line graph LG. The sandpile group is an abelian group associated to a directed graph, whose order is the number of oriented spanning trees rooted at a fixed vertex. In the case when G is regular of degree k, we show that the sandpile group of G is isomorphic to the quotient of the sandpile group of LG by its k-torsion subgroup. As a corollary we compute the sandpile groups of two families of graphs widely studied in computer science, the de Bruijn graphs and Kautz graphs.     

Distance unimodular equivalence of graphs

Let G be a connected graph and D(G) be its distance matrix. In this article, the Smith normal forms of the integer matrices D(G) are determined for trees, wheels, cycles, complements of cycles and are reduced for complete multipartite graphs.