Automorphisms of coverings of strongly regular graphs with parameters (81,20,1,6)

The possible orders and subgraphs of fixed points of the automorphisms of distance-regular graphs of diameter 4 which are r-coverings of a strongly regular graph with parameters (81, 20, 1, 6) for r ∈ {2, 3, 6} are found. It is proved that, if the automorphism group of a covering of the above type acts transitively on the set of vertices of the graph, then r = 3.     

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.     

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.     

A remark on partial linear spaces of girth 5 with an application to strongly regular graphs

We derive a lower bound on the number of points of a partial linear space of girth 5. As an application, certain strongly regular graphs with=2 are ruled out by observing that the first subconstituents are partial linear spaces.     

Some new strongly regular graphs

We show that three pairwise 4-regular graphs constructed by the second author are members of infinite families.     

5-chromatic strongly regular graphs

In this paper, we begin the determination of all primitive strongly regular graphs with chromatic number equal to 5. Using eigenvalue techniques, we show that there are at most 43 possible parameter sets for such a graph. For each parameter set, we must decide which strongly regular graphs, if any, possessing the set are 5-chromatic. In this way, we deal completely with 34 of these parameter sets using eigenvalue techniques and computer enumerations.     

Partitions of sets of two-fold triple systems,and their relation to some strongly regular graphs

LetX be a set ofv + 1 elements, wherev 0 or 1 (mod 3). If two copies of the collection of triples chosen fromX can be partitioned intov + 1 mutually disjoint two-fold triple systems, each based on a differentv-subset ofX, we say they form an overlarge set of two-fold triple systems, denoted byOS(TTS(v)). In this paper, we give the first construction of anOS(TTS(10)). We then investigate the properties of the uniqueOS(TTS(6)) and obtain:

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     

Independent sets in regular graphs

Lower and upper bounds for the maximal number of independent vertices in a regular graph are obtained, it is shown that the bounds are best possible. Some properties of regular graphs concerning the property ℋ defined below are investigated. This paper is to be a part of the author’s Ph. D. thesis written under the supervision of Prof. B. Grünbaum at the Hebrew University of Jerusalem.     

Unimodular lattices and strongly regular graphs

One finds a relationship between the theory of unimodular lattices and the theory of strongly regular graphs. For a unimodular, even lattice of dimension 32 having a system of roots of type A₁ one constructs a strongly regular graph with parameters n=8184, a=7595, c=7042, d=7130. The graphs that arise from certain Steiner sixtuple systems have the same parameters. One also constructs strongly regular graphs for extremal lattices of dimension 48.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 129, pp. 30–38, 1983.     

Parallelogram-free distance-regular graphs having completely regular strongly regular subgraphs

Let Γ=(X,R) be a distance-regular graph of diameter d. A parallelogram of length i is a 4-tuple xyzw consisting of vertices of Γ such that ?(x,y)=?(z,w)=1, ?(x,z)=i, and ?(x,w)=?(y,w)=?(y,z)=i?1. A subset Y of X is said to be a completely regular code if the numbers

$\pi_{i,j}=|\Gamma_{j}(x)\cap Y|\quad (i,j\in \{0,1,\ldots,d\})$

depend only on i=?(x,Y) and j. A subset Y of X is said to be strongly closed if

$\{x\mid \partial(u,x)\leq \partial(u,v),\partial(v,x)=1\}\subset Y,\mbox{ whenever }u,v\in Y.$

Hamming graphs and dual polar graphs have strongly closed completely regular codes. In this paper, we study parallelogram-free distance-regular graphs having strongly closed completely regular codes. Let Γ be a parallelogram-free distance-regular graph of diameter d≥4 such that every strongly closed subgraph of diameter two is completely regular. We show that Γ has a strongly closed subgraph of diameter d?1 isomorphic to a Hamming graph or a dual polar graph. Moreover if the covering radius of the strongly closed subgraph of diameter two is d?2, Γ itself is isomorphic to a Hamming graph or a dual polar graph. We also give an algebraic characterization of the case when the covering radius is d?2.

     

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.