Strongly regular Cayley graphs from partitions of subdifference sets of the Singer difference sets

In this paper, we give a new lifting construction of “hyperbolic” type of strongly regular Cayley graphs. Also we give new constructions of strongly regular Cayley graphs over the additive groups of finite fields based on partitions of subdifference sets of the Singer difference sets. Our results unify some recent constructions of strongly regular Cayley graphs related to m-ovoids and i-tight sets in finite geometry. Furthermore, some of the strongly regular Cayley graphs obtained in this paper are new or nonisomorphic to known strongly regular graphs with the same parameters.     

On quasi-strongly regular graphs

We study the quasi-strongly regular graphs, which are a combinatorial generalization of the strongly regular and the distance regular graphs. Our main focus is on quasi-strongly regular graphs of grade 2. We prove a “spectral gap”-type result for them which generalizes Seidel's well-known formula for the eigenvalues of a strongly regular graph. We also obtain a number of necessary conditions for the feasibility of parameter sets and some structural results. We propose the heuristic principle that the quasi-strongly regular graphs can be viewed as a “lower-order approximation” to the distance regular graphs. This idea is illustrated by extending a known result from the distance-regular case to the quasi-strongly regular case. Along these lines, we propose a number of conjectures and open problems. Finally, we list the all the proper connected quasi-strongly graphs of grade 2 with up to 12 vertices.     

On quasi-strongly regular graphs

We study the quasi-strongly regular graphs, which are a combinatorial generalization of the strongly regular and the distance regular graphs. Our main focus is on quasi-strongly regular graphs of grade 2. We prove a “spectral gap”-type result for them which generalizes Seidel's well-known formula for the eigenvalues of a strongly regular graph. We also obtain a number of necessary conditions for the feasibility of parameter sets and some structural results. We propose the heuristic principle that the quasi-strongly regular graphs can be viewed as a “lower-order approximation” to the distance regular graphs. This idea is illustrated by extending a known result from the distance-regular case to the quasi-strongly regular case. Along these lines, we propose a number of conjectures and open problems. Finally, we list the all the proper connected quasi-strongly graphs of grade 2 with up to 12 vertices.     

Type-II matrices in weighted Bose–Mesner algebras of ranks 2 and 3

Type-II matrices are nonzero complex matrices that were introduced in connection with spin models for link invariants. Type-II matrices have been found in connection with symmetric designs, sets of equiangular lines, strongly regular graphs, and some distance regular graphs. We investigate weighted complete and strongly regular graphs, and show that type-II matrices arise in this setting as well.     

Strongly regular Cayley graphs,skew Hadamard difference sets,and rationality of relative Gauss sums

In this paper, we give constructions of strongly regular Cayley graphs and skew Hadamard difference sets. Both constructions are based on choosing cyclotomic classes in finite fields. Our results generalize ten of the eleven sporadic examples of cyclotomic strongly regular graphs given by Schmidt and White (2002) [23] and several subfield examples into infinite families. These infinite families of strongly regular graphs have new parameters. The main tools that we employed are relative Gauss sums instead of explicit evaluations of Gauss sums.     

A generalization of Wallis-Fon-Der-Flaass construction of strongly regular graphs

In this paper the Wallis-Fon-Der-Flaass construction of strongly regular graphs is generalized. As a result new prolific series of strongly regular graphs are obtained. Some of them have new parameters. The author was partially supported by the Israeli Ministry of Absorption.     

Star partitions and the graph isomorphism problem

A canonical basis of Rⁿ associated with a graph G on n vertices has been defined in [15] in connection with eigenspaces and star partitions of G. The canonical star basis together with eigenvalues of G determines G to an isomorphism. We study algorithms for finding the canonical basis and some of its variations. The emphasis is on the following three special cases; graphs with distinct eigenvalues, graphs with bounded eigenvalue multiplicities and strongly regular graphs. We show that the procedure is reduced in some parts to special cases of some well known combinatorial optimization problems, such as the maximal matching problem. the minimal cut problem, the maximal clique problem etc. This technique provides another proof of a result of L. Babai et al. [2] that isomorphism testing for graphs with bounded eigenvalue multiplicities can be performend in a polynomial time. We show that the canonical basis in strongly regular graphs is related to the graph decomposition into two strongly regular induced subgraphs. Examples of distinguishing between cospectral strongly regular graphs by means of the canonical basis are provided. The behaviour of star partitions of regular graphs under operations of complementation and switching is studied.     

A switching for all strongly regular collinearity graphs from polar spaces

We describe a general construction of strongly regular graphs from the collinearity graph of a finite classical polar spaces of rank at least 3 over a finite field of order q. We show that these graphs are non-isomorphic to the collinearity graphs and have the same parameters. For most of these parameters, the collinearity graphs were the only known examples, and so many of our examples are new.     

Constructions of 1 1/2-designs from symplectic geometry over finite fields

In this paper, we construct some 1(1/2)-designs, which are also known as partial geometric designs, using totally isotropic subspaces of the symplectic space and generalized symplectic graphs. Furthermore, these 1(1/2)-designs yield six infinite families of directed strongly regular graphs.     

Strongly regular Cayley graphs and rationality of relative Gauss sums

In this note, we give a construction of strongly regular Cayley graphs. The presented construction is based on choosing cyclotomic classes in finite fields, and our results generalize ten of the eleven sporadic examples of cyclotomic strongly regular graphs given by Schmidt and White [B. Schmidt, C. White, All two-weight irreducible cyclic codes, Finite Fields Appl. 8 (2002), 321–367] into infinite families. These infinite families of strongly regular graphs have new parameters. The main tools that we employed are relative Gauss sums instead of explicit evaluations of Gauss sums.     

Strongly Regular Decompositions of the Complete Graph

We study several questions about amorphic association schemes and other strongly regular decompositions of the complete graph. We investigate how two commuting edge-disjoint strongly regular graphs interact. We show that any decomposition of the complete graph into three strongly regular graphs must be an amorphic association scheme. Likewise we show that any decomposition of the complete graph into strongly regular graphs of (negative) Latin square type is an amorphic association scheme. We study strongly regular decompositions of the complete graph consisting of four graphs, and find a primitive counterexample to A.V. Ivanov's conjecture which states that any association scheme consisting of strongly regular graphs only must be amorphic.     

Ternary codes from the strongly regular (45, 12, 3, 3) graphs and orbit matrices of 2-(45, 12, 3) designs

The enumeration of strongly regular graphs with parameters (45, 12, 3, 3) has been completed, and it is known that there are 78 non-isomorphic strongly regular (45, 12, 3, 3) graphs. A strongly regular graph with these parameters is a symmetric (45, 12, 3) design having a polarity with no absolute points. In this paper we examine the ternary codes obtained from the adjacency (resp. incidence) matrices of these graphs (resp. designs), and those of their corresponding derived and residual designs. Further, we give a generalization of a result of Harada and Tonchev on the construction of non-binary self-orthogonal codes from orbit matrices of block designs under an action of a fixed-point-free automorphism of prime order. Using the generalized result we present a complete classification of self-orthogonal ternary codes of lengths 12, 13, 14, and 15, obtained from non-fixed parts of orbit matrices of symmetric (45, 12, 3) designs admitting an automorphism of order 3. Several of the codes obtained are optimal or near optimal for the given length and dimension. We show in addition that the dual codes of the strongly regular (45, 12, 3, 3) graphs admit majority logic decoding.     

Distance–regular graphs having the M-property

We analyse when the Moore–Penrose inverse of the combinatorial Laplacian of a distance–regular graph is an M-matrix; that is, it has non-positive off-diagonal elements or, equivalently when the Moore–Penrose inverse of the combinatorial Laplacian of a distance–regular graph is also the combinatorial Laplacian of another network. When this occurs we say that the distance–regular graph has the M-property. We prove that only distance–regular graphs with diameter up to three can have the M-property and we give a characterization of the graphs that satisfy the M-property in terms of their intersection array. Moreover, we exhaustively analyse strongly regular graphs having the M-property and we give some families of distance–regular graphs with diameter three that satisfy the M-property. Roughly speaking, we prove that all distance–regular graphs with diameter one; about half of the strongly regular graphs; only some imprimitive distance–regular graphs with diameter three, and no distance–regular graphs with diameter greater than three, have the M-property. In addition, we conjecture that no primitive distance–regular graph with diameter three has the M-property.     

Cores of Geometric Graphs

Cameron and Kazanidis have recently shown that rank-three graphs are either cores or have complete cores, and they asked whether this holds for all strongly regular graphs. We prove that this is true for the point graphs and line graphs of generalized quadrangles and that when the number of points is sufficiently large, it is also true for the block graphs of Steiner systems and orthogonal arrays.     

Strongly regular graphs with non-trivial automorphisms

The possible existence of 16 parameter sets for strongly regular graphs with 100 or less vertices is still unknown. In this paper, we outline a method to search for strongly regular graphs by assuming a non-trivial automorphism of prime order. Among these unknown parameter sets, we eliminated many possible automorphisms, but some small prime orders still remain. We also found 6 new strongly regular graphs with parameters (49,18,7,6).     

Disconnecting strongly regular graphs

In this paper, we show that the minimum number of vertices whose removal disconnects a connected strongly regular graph into non-singleton components equals the size of the neighborhood of an edge for many graphs. These include block graphs of Steiner 2-designs, many Latin square graphs and strongly regular graphs whose intersection parameters are at most a quarter of their valency.     

Some results on strongly regular graphs from unions of cyclotomic classes

In this paper, we construct some families of strongly regular graphs on finite fields by using unions of cyclotomic classes and index 2 Gauss sums. New infinite families of strongly regular graphs are found.     

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.     

Strongly Regular Semi-Cayley Graphs

We consider strongly regular graphs = (V, E) on an even number, say 2n, of vertices which admit an automorphism group G of order n which has two orbits on V. Such graphs will be called strongly regular semi-Cayley graphs. For instance, the Petersen graph, the Hoffman–Singleton graph, and the triangular graphs T(q) with q 5 mod 8 provide examples which cannot be obtained as Cayley graphs. We give a representation of strongly regular semi-Cayley graphs in terms of suitable triples of elements in the group ring Z G. By applying characters of G, this approach allows us to obtain interesting nonexistence results if G is Abelian, in particular, if G is cyclic. For instance, if G is cyclic and n is odd, then all examples must have parameters of the form 2n = 4s ² + 4s + 2, k = 2s ² + s, = s ² – 1, and = s ²; examples are known only for s = 1, 2, and 4 (together with a noncyclic example for s = 3). We also apply our results to obtain new conditions for the existence of strongly regular Cayley graphs on an even number of vertices when the underlying group H has an Abelian normal subgroup of index 2. In particular, we show the nonexistence of nontrivial strongly regular Cayley graphs over dihedral and generalized quaternion groups, as well as over two series of non-Abelian 2-groups. Up to now these have been the only general nonexistence results for strongly regular Cayley graphs over non-Abelian groups; only the first of these cases was previously known.     

Strongly regular graphs constructed from <Emphasis Type="Italic">p</Emphasis>-ary bent functions

In this paper, we generalize the construction of strongly regular graphs in Tan et al. (J. Comb. Theory, Ser. A 117:668–682, 2010) from ternary bent functions to p-ary bent functions, where p is an odd prime. We obtain strongly regular graphs with three types of parameters. Using certain non-quadratic p-ary bent functions, our constructions can give rise to new strongly regular graphs for small parameters.