On the p-Rank of the Adjacency Matrices of Strongly Regular Graphs

Let be a strongly regular graph with adjacency matrix A. Let I be the identity matrix, and J the all-1 matrix. Let p be a prime. Our aim is to study the p-rank (that is, the rank over , the finite field with p elements) of the matrices M = aA + bJ + cI for integral a, b, c. This note is based on van Eijl [8].     

The Displacement and Split Decompositions for a Q-Polynomial Distance-regular Graph

Let denote a Q-polynomial distance-regular graph with diameter at least three and standard module V. We introduce two direct sum decompositions of V. We call these the displacement decomposition for and the split decomposition for . We describe how these decompositions are related.     

Distance-Regular Graphs Related to the Quantum Enveloping Algebra of sl(2)

We investigate a connection between distance-regular graphs and U _q(sl(2)), the quantum universal enveloping algebra of the Lie algebra sl(2). Let be a distance-regular graph with diameter d 3 and valency k 3, and assume is not isomorphic to the d-cube. Fix a vertex x of , and let (x) denote the Terwilliger algebra of with respect to x. Fix any complex number q {0, 1, –1}. Then is generated by certain matrices satisfying the defining relations of U _q(sl(2)) if and only if is bipartite and 2-homogeneous.     

On thep-ranks of net graphs

Let be ak-net of ordern with line-point incidence matrixN and letA be the adjacency matrix of its collinearity graph. In this paper we study thep-ranks (that is, the rank over ) of the matrixA+kl withp a prime dividingn. SinceA+kI=N ^T N thesep-ranks are closely related to thep-ranks ofN. Using results of Moorhouse on thep-ranks ofN, we can determiner _p (A+kI) if is a 3-net (latin square) or a desarguesian net of prime order. On the other hand we show how results for thep-ranks ofA+kI can be used to get results for thep-ranks ofN, especially in connection with the Moorhouse conjecture. Finally we generalize the result of Moorhouse on thep-rank ofN for desarguesian nets of orderp a bit to special subnets of the desarguesian affine plane of orderp ^e .The author is financially supported by the Cooperation Centre Tilburg and Eindhoven Universities.     

The spectral excess theorem for distance-regular graphs having distance-<Emphasis Type="Italic">d</Emphasis> graph with fewer distinct eigenvalues

Let \(\Gamma \) be a distance-regular graph with diameter d and Kneser graph \(K=\Gamma _d\), the distance-d graph of \(\Gamma \). We say that \(\Gamma \) is partially antipodal when K has fewer distinct eigenvalues than \(\Gamma \). In particular, this is the case of antipodal distance-regular graphs (K with only two distinct eigenvalues) and the so-called half-antipodal distance-regular graphs (K with only one negative eigenvalue). We provide a characterization of partially antipodal distance-regular graphs (among regular graphs with \(d+1\) distinct eigenvalues) in terms of the spectrum and the mean number of vertices at maximal distance d from every vertex. This can be seen as a more general version of the so-called spectral excess theorem, which allows us to characterize those distance-regular graphs which are half-antipodal, antipodal, bipartite, or with Kneser graph being strongly regular.     

A Computer-Assisted Proof of the Uniqueness of the Perkel Graph

The Perkel graph is a distance-regular graph of order 57, degree 6 and diameter 3, with intersection array (6, 5, 2; 1, 1, 3). We describe a computer assisted proof that every graph with this intersection array is isomorphic to the Perkel graph. The computer proof relies heavily on the fact that the minimal idempotents for , and their submatrices, are positive semidefinite.To minimize the risk of computer errors we have used two different methods to establish the same theorem and as an added precaution large parts of the corresponding programs were written by different authors.The first method generates plausible subgraphs induced by all vertices at distance 3 from a fixed vertex of and then tries to extend each of the generated graphs to a full graph with the given intersection array.The second method generates possible neighborhoods for a pentagon in . It turns out that every such pentagon can be extended to a Petersen graph in . We then prove mathematically that there is, up to isomorphism, only a single graph with this property.     

Bipartite <Emphasis Type="Italic">Q</Emphasis>-Polynomial Distance-Regular Graphs

Let denote a bipartite distance-regular graph with diameter D12. We show is Q-polynomial if and only if one of the following (i)–(iv) holds: (i) is the ordinary 2D-cycle. (ii) is the Hamming cube H(D,2). (iii) is the antipodal quotient of H(2D,2). (iv) The intersection numbers of satisfy where q is an integer at least 2. We obtain the above result using the Terwilliger algebra of .AMS 1991 Subject Classification: Primary 05E30Final version received: April 10, 2003     

Tiling the torus and other space forms

We consider graphs on two-dimensional space forms which are quotient graphs /F, where is an infinite, 3-connected, face, vertex, or edge transitive planar graph andF is a subgroup of Aut(), all of whose elements act freely on . The enumeration of quotient graphs with transitivity properties reduces to computing the normalizers in Aut() of the subgroupsF. Results include: all isogonal toriodal polyhedra belong to the two families found by Grünbaum and Shephard; there are no transitive graphs on the Möbius band; there is a graph on the Klein bottle whose automorphism group acts transitively on its faces, edges, and vertices.This paper is an expanded version of a lecture presented to the Conference on Combinatorial Geometry, Oberwolfach, Germany, September 1984.     

Mortality of iterated Gallai graphs

For a finite or infinite graphG, theGallai graph (G) ofG is defined as the graph whose vertex set is the edge setE(G) ofG; two distinct edges ofG are adjacent in (G) if they are incident but do not span a triangle inG. For any positive integert, thetth iterated Gallai graph ^t (G) ofG is defined by ( ^t–1(G)), where ⁰(G):=G. A graph is said to beGallai-mortal if some of its iterated Gallai graphs finally equals the empty graph. In this paper we characterize Gallai-mortal graphs in several ways.     

On the Normality of Cayley Digraphs of Valency 2 on Non-Abelian Group of Odd Order

In this paper, we prove that the Cayley digraph = Cay(G, S) of valency 2 on non-abelian group G of odd order is normal if the automorphism group of A(), a graph constructed from by using the method presented in the paper, is primitive on the vertices set V(A(). We also prove that the Cayley digraphs of valency 2 on non-abelian group of order pq² are normal, where p and q are distinct odd primes.AMS Subject Classification (2000) 05C25 20B25Supported by the National Natural Science Foundation of China (Grant no. 19971086) and the Doctoral Program Foundation of the National Education Department of China.     

Graphs connected to the hadamard manifold and groups of its isometries

Three graphs are associated to the Hadamard manifold X and the discrete group of its isometries .The set of vertices of the first graph is X itself, of the second all the almost nilpotent subgroups in ,and of the third the geometric invariants of the vertices of the second graph such as the fixed point set, collections of invariant lines, and so on. The group acts on all three graphs and there exist images of these graphs that are equivariant with resepct to these actions. This formalism allows us to adduce a simple proof of the following theorem. Let M be an n-dimensional complete Riemannian manifold with sectional curvatures 1 K 0 and satisfying the visibility axiom. Then there exists a point p M such that the injectivity radius Inj Rad(p) c(n), where the constant c(n) > 0 depends only on n. Other results obtained with the help of this formalism are also given. Translated from Ukrainskii Geometricheskii Sbornik, No. 34, pp. 19–31, 1991.     

On Distance-Regular Graphs with Height Two

Let be a distance-regular graph with diameter at least three and height h = 2, where . Suppose that for every in and in _d(), the induced subgraph on _d() ₂() is a clique. Then is isomorphic to the Johnson graph J(8, 3).     

Distance mean-regular graphs

We introduce the concept of distance mean-regular graph, which can be seen as a generalization of both vertex-transitive and distance-regular graphs. Let \(\Gamma \) be a graph with vertex set V, diameter D, adjacency matrix \(\varvec{A}\), and adjacency algebra \(\mathcal{A}\). Then, \(\Gamma \) is distance mean-regular when, for a given \(u\in V\), the averages of the intersection numbers \(p_{ij}^h(u,v)=|\Gamma _i(u)\cap \Gamma _j(v)|\) (number of vertices at distance i from u and distance j from v) computed over all vertices v at a given distance \(h\in \{0,1,\ldots ,D\}\) from u, do not depend on u. In this work we study some properties and characterizations of these graphs. For instance, it is shown that a distance mean-regular graph is always distance degree-regular, and we give a condition for the converse to be also true. Some algebraic and spectral properties of distance mean-regular graphs are also investigated. We show that, for distance mean regular-graphs, the role of the distance matrices of distance-regular graphs is played for the so-called distance mean-regular matrices. These matrices are computed from a sequence of orthogonal polynomials evaluated at the adjacency matrix of \(\Gamma \) and, hence, they generate a subalgebra of \(\mathcal{A}\). Some other algebras associated to distance mean-regular graphs are also characterized.     

Auslander–Reiten Components Containing Cones

Let A be a locally finite Abelian R-category with Auslander–Reiten sequences and with Auslander–Reiten quiver (A). We give a criterion for Auslander–Reiten components to contain a cone and apply this result to various categories.     

On a signless Laplacian spectral characterization of -shape trees

Let M be an associated matrix of a graph G (the adjacency, Laplacian and signless Laplacian matrix). Two graphs are said to be cospectral with respect to M if they have the same M spectrum. A graph is said to be determined by M spectrum if there is no other non-isomorphic graph with the same spectrum with respect to M. It is shown that T-shape trees are determined by their Laplacian spectra. Moreover among them those are determined by their adjacency spectra are characterized. In this paper, we identify graphs which are cospectral to a given T-shape tree with respect to the signless Laplacian matrix. Subsequently, T-shape trees which are determined by their signless Laplacian spectra are identified.     

Distance-Regular Graphs with c i = b d-i and Antipodal Double Covers

Let be a distance-regular graph of diameter d and valency k > 2. Suppose there exists an integer s with d 2s such that c _i = b _d-i for all 1 i s. Then is an antipodal double cover.     

Cohomologie lp et produits amalgamés

The first l_p-cohomology group of a hyperbolic groupe induces on the boundary of equivalence relations which are invariant by quasi-isometries. We study these equivalence relations in case of some amalgamated products =A _{* c} B.     

Tight Distance-Regular Graphs

We consider a distance-regular graph with diameter d 3 and eigenvalues k = ₀ > ₁ > ... > _d . We show the intersection numbers a ₁, b ₁ satisfy

On a Rank Five Geometry of Meixner for the Mathieu Group M12

We construct a rank five residually connected and firm geometry on which the Mathieu group M ₁₂ acts flag-transitively and residually weakly primitively (RWPRI). The group M ₁₂ is the group of automorphisms of and Aut(M ₁₂) is the correlation group of , in particular is self-dual. The diagram of is the following. Moreover satisfies the conditions (IP)₂ and (2T)₁. As a corollary, we obtain that the (RWPRI+(IP)₂)-rank of M ₁₂ is 5.     

On groups of polynomial subgroup growth

Summary Let be a finitely generated group anda _n ()=the number of its subgroups of indexn. We prove that, assuming is residually nilpotent (e.g., linear), thena _n () grows polynomially if and only if is solvable of finite rank. This answers a question of Segal. The proof uses a new characterization ofp-adic analytic groups, the theory of algebraic groups and the Prime Number Theorem. The method can be applied also to groups of polynomial word growth.Oblatum 1-VII-1989 & 7-VI-1990