Some Elementary Ramanujan Graphs

We give elementary constructions of two infinite families of Ramanujan graphs of unbounded degree. The first uses the geometry of buildings over finite fields, and the second uses triangulations of modular curves.Mathematics Subject Classiffications (2000). Primary: 05C25; secondary: 05C50, 51E24     

Ramanujan Graphs with Small Girth

We construct an innite family of (q + 1)-regular Ramanujan graphs X _n of girth 1. We also give covering maps X _n+1 X _n such that the minimal common covering of all the X _n s is the universal covering tree.     

On Parameters of Some Graphs from Finite Fields

We generalize the constructon of F. R. Chung of graphs from finite fields and estimate their parameters with the help of a new bound of exponential sums due to G. I. Perel'muter and the author.     

On the Spectra of Certain Graphs Arising from Finite Fields

Cayley graphs on a subgroup ofGL(3,p),p>3 a prime, are defined and their properties, particularly their spectra, studied. It is shown that these graphs are connected, vertex-transitive, nonbipartite, and regular, and their degrees are computed. The eigenvalues of the corresponding adjacency matrices depend on the representations of the group of vertices. The “1-dimensional” eigenvalues can be completely described, while a portion of the “higher dimensional” eigenfunctions are discrete analogs of Bessel functions. A particular subset of these graphs is conjectured to be Ramanujan and this is verified for over 2000 graphs. These graphs follow a construction used by Terras on a subgroup ofGL(2,p). This method can be extended further to construct graphs using a subgroup ofGL(n, p) forn≥4. The 1-dimensional eigenvalues in this case can be expressed in terms of the 1-dimensional eigenvalues of graphs fromGL(2,p) andGL(3,p); this part of the spectra alone is sufficient to show that forn≥4, the graphs fromGL(n, p) are not in general Ramanujan.     

Finite Euclidean graphs and Ramanujan graphs

We consider finite analogues of Euclidean graphs in a more general setting than that considered in [A. Medrano, P. Myers, H.M. Stark, A. Terras, Finite analogues of Euclidean space, J. Comput. Appl. Math. 68 (1996) 221-238] and we obtain many new examples of Ramanujan graphs. In order to prove these results, we use the previous work of [W.M. Kwok, Character tables of association schemes of affine type, European J. Combin. 13 (1992) 167-185] calculating the character tables of certain association schemes of affine type. A key observation is that we can obtain better estimates for the ordinary Kloosterman sum K(a,b;q). In particular, we always achieve , and in many (but not all) of the cases, instead of the well known . Also, we use the ideas of controlling association schemes, and the Ennola type dualities, in our previous work on the character tables of commutative association schemes. The method in this paper will be used to construct many more new examples of families of Ramanujan graphs in the subsequent paper.     

Algebraic Shifting of Finite Graphs

In the present article, for bipartite graphs and chordal graphs, their exterior algebraic shifted graph and their symmetric algebraic shifted graph are studied. First, we will determine the symmetric algebraic shifted graph of complete bipartite graphs. It turns out that for a ≥ 3 and b ≥ 3, the exterior algebraic shifted graph of the complete bipartite graph K _a,b of size a, b is different from the symmetric algebraic shifted graph of K _a,b . Second, we will show that the exterior algebraic shifted graph of any chordal graph G coincides with the symmetric algebraic shifted graph of G. In addition, it will be shown that the exterior algebraic shifted graph of any chordal graph G is equal to some combinatorial shifted graph of G.     

Applications of Finite Fields to Combinatorics and Finite Geometries

We survey some applications of finite fields to finite geometries in part A and to combinatorics and error-correcting codes in parts B and C.     

Arithmetic Graphs and Classes of Finite Groups

Siberian Mathematical Journal - An arithmetic graph function is a mapping associating to a finite group G the graph whose vertices are the divisors of |G|. We formulate and study the problem of...     

Transitive,Locally Finite Median Graphs with Finite Blocks

The subject of this paper are infinite, locally finite, vertex-transitive median graphs. It is shown that the finiteness of the Θ-classes of such graphs does not guarantee finite blocks. Blocks become finite if, in addition, no finite sequence of Θ-contractions produces new cut-vertices. It is proved that there are only finitely many vertex-transitive median graphs of given finite degree with finite blocks. An infinite family of vertex-transitive median graphs with finite intransitive blocks is also constructed and the list of vertex-transitive median graphs of degree four is presented. Sandi Klavžar: Supported by the Ministry of Science of Slovenia under the grant P1-0297. The author is also with the Faculty of Mathematics and Natural Sciences, University of Maribor, Slovenia and the Institute of Mathematics, Physics and Mechanics, Ljubljana.     

On Ramanujan Sums over a Dedekind Domain with Finite Norm Property

In this paper, we consider Ramanujan’s sums over arbitrary Dedekind domain with finite norm property. We define the Ramanujan’s sums η(a, A) and η(B, A), where a is an arbitrary element in a Dedekind domain, B is an ideal and A is a non-zero ideal. In particular, we discuss the Kluyver formula and Hèolder formula for η(a, A) and η(B, A). We also prove the reciprocity formula enjoyed byη(B, A) and the orthogonality relations for η(a, A) in the last two parts.     

Integral Cayley Graphs over Finite Groups

We prove that the spectrum of a Cayley graph over a finite group with a normal generating set S containing with every its element s all generators of the cyclic group(s)is integral.In particular,a Cayley graph of a 2-group generated by a normal set of involutions is integral.We prove that a Cayley graph over the symmetric group of degree n no less than 2 generated by all transpositions is integral.We find the spectrum of a Cayley graph over the alternating group of degree n no less than 4 with a generating set of 3-cycles of the form(k i j)with fixed k,a s{-n+1,1-n+1,2^2-n+1,...,(n-1)2-n+1}.     

On Isomorphisms of Finite Cayley Graphs

A Cayley graph Cay(G,S) of a groupGis called a CI-graph if wheneverTis another subset ofGfor which Cay(G,S) Cay(G,T), there exists an automorphism σ ofGsuch thatS^σ = T. For a positive integerm, the groupGis said to have them-CI property if all Cayley graphs ofGof valencymare CI-graphs; further, ifGhas thek-CI property for allk ≤ m, thenGis called anm-CI-group, and a |G|-CI-groupGis called a CI-group. In this paper, we prove that Ais not a 5-CI-group, that SL(2,5) is not a 6-CI-group, and that all finite 6-CI-groups are soluble. Then we show that a nonabelian simple group has the 4-CI property if and only if it is A₅, and that no nonabelian simple group has the 5-CI property. Also we give nine new examples of CI-groups of small order, which were found to be CI-groups with the assistance of a computer.     

The Total Graphs of Finite Rings

In this paper we extend the study of total graphs τ(R) to noncommutative finite rings R. We prove that τ(R) is connected if and only if R is not local, and we see that in that case τ(R) is always Hamiltonian. We also find an upper bound for the domination number of τ(R) for all finite rings R.     

Enumerating Planar Locally Finite Cayley Graphs

We characterize the set of planar locally finite Cayley graphs, and give a finite representation of these graphs by a special kind of finite state automata called labeling schemes. As a result, we are able to enumerate and describe all planar locally finite Cayley graphs of a given degree. This analysis allows us to solve the problem of decision of the locally finite planarity for a word-problem-decidable presentation.Mathematics Subject Classiffications (2000). 20F05, 20F10, 20F65, 05C25     

Decomposing Ends of Locally Finite Graphs

An important invariant of translations of infinite locally finite graphs is that of a direction as introduced by Halin . This invariant gives not much information if the translation is not a proper one. A new refined concept of directions is investigated. A double ray D of a graph X is said to be metric, if the distance metrics in D and X on V(D) are equivalent. It is called geodesic, if these metrics are equal. The translations leaving some metric double ray invariant are characterized. Using a result of Polat and Watkins , we characterize the translations leaving some geodesic double ray invariant.     

Irreducibility Criterion Over Finite Fields

The aim of this article is to prove the irreducibility of the polynomial Λ(Y) = Y ^d  + λ _d?1 Y ^d?1 + … + λ₀ over 𝔽 _q [X] where λ _i ∈ 𝔽 _q [X] and deg λ _d?1 > deg λ _i for each i ≠ d ? 1. We discuss in particular connections between the irreducible polynomials Λ and the number of Pisot elements in the case of formal power series.