Search

We construct a new family of strongly regular graphs with the same parameters as the strongly regular graphs D 5 , 5 (q). The construction can be seen as a variant of the construction of twisted Grassmann graphs by Van Dam and Koolen. [ABSTRACT FROM AUTHOR]

Let G be a finite simple graph with λ as an eigenvalue (i.e. an eigenvalue of the adjacency matrix of G), and let H be a star complement for λ in G. Motivated by a controllability condition, we say that H is a strong star complement for λ if G and H have no eigenvalue in common. We explore this concept in the context of line graphs, exceptional graphs, strongly regular graphs and graphs with a prescribed star complement. [ABSTRACT FROM AUTHOR]

In this paper, we give a construction of strongly regular graphs from pseudocyclic association schemes, which is a common generalization of two constructions given by Fujisaki (2004). Furthermore, we prove that the pseudocyclic association scheme arising from the action of PGL(2, q) to the set of exterior lines in PG(2, q), called the elliptic scheme, under the assumption that q = 2 m with m an odd prime satisfies the condition of our new construction. As a consequence, we obtain a new infinite family of strongly regular graphs of Latin square type with non-prime-power number of vertices. [ABSTRACT FROM AUTHOR]

We introduce the notion of q -analogs of strongly regular graphs and give several examples of such structures. We prove a necessary condition on the parameters, show the connection to designs over finite fields, and present a classification. [ABSTRACT FROM AUTHOR]

Strongly regular graphs (SRGs) provide a fertile area of exploration in algebraic combinatorics, integrating techniques in graph theory, linear algebra, group theory, finite fields, finite geometry, and number theory. Of particular interest are those SRGs with a large automorphism group. If an automorphism group acts regularly (sharply transitively) on the vertices of the graph, then we may identify the graph with a subset of the group, a partial difference set (PDS), which allows us to apply techniques from group theory to examine the graph. Much of the work over the past four decades has concentrated on abelian PDSs using the powerful techniques of character theory. However, little work has been done on nonabelian PDSs. In this paper we point out the existence of genuinely nonabelian PDSs, that is, PDSs for parameter sets where a nonabelian group is the only possible regular automorphism group. We include methods for demonstrating that abelian PDSs are not possible for a particular set of parameters or for a particular SRG. Four infinite families of genuinely nonabelian PDSs are described, two of which—one arising from triangular graphs and one arising from Krein covers of complete graphs constructed by Godsil—are new. We also include a new nonabelian PDS found by computer search and present some possible future directions of research. [ABSTRACT FROM AUTHOR]

In this paper we construct distance-regular graphs admitting a vertex transitive action of the five sporadic simple groups discovered by E. Mathieu, the Mathieu groups M 11 , M 12 , M 22 , M 23 and M 24 . From the binary code spanned by an adjacency matrix of the strongly regular graph with parameters (176,70,18,34) we obtain block designs having the full automorphism groups isomorphic to the Higman-Sims finite simple group. Moreover, from that code we obtain eight 2-designs having the full automorphism group isomorphic to M 22 , whose existence cannot be explained neither by the Assmus-Mattson theorem nor by a transitivity argument. Further, we discuss a possibility of permutation decoding of the codes spanned by adjacency matrices of the graphs constructed and find small PD-sets for some of the codes. [ABSTRACT FROM AUTHOR]

A graph is called an edge-regular graph with parameters (n, k, a) if it is a k-regular graph with n vertices and any two adjacent vertices have a common neighbours. A quasi-strongly regular graph with parameters (n , k , a ; c 1 , c 2) , denoted by QSRG (n , k , a ; c 1 , c 2) , is an edge-regular graph with parameters (n, k, a) in which any two non-adjacent vertices have c 1 or c 2 common neighbours. A quasi-strongly regular graph is called a strictly quasi-strongly regular graph if it is neither a strongly regular graph nor a Deza graph. The purpose of our research is to complete the structural characterization of strictly QSRG (n , k , a ; k - 2 , c 2) . In an earlier paper, we characterised QSRG (n , k , a ; k - 2 , c 2) satisfying a < k - 5 and l 1 > 2 , where l 1 is the number of vertices with k - 2 common neighbours with a given vertex. In the present paper, we investigate the structural characterization of strictly QSRG (n , k , a ; k - 2 , c 2) satisfying a ≥ k - 5 . [ABSTRACT FROM AUTHOR]

Using an approach from finite group representation theory we construct quaternary non-projective codes with parameters [693, 6, 480]4, [1386, 6, 1008]4, [2016, 6, 1488]4, quaternary projective codes with parameters [231, 6, 160]4, [462, 6, 336]4 and [672, 6, 496]4 and binary projective codes with parameters [693, 12, 320]2, [1386, 12, 672]2, [2016, 12, 992]2 as examples of two-weight codes on which a finite almost quasisimple group of sporadic type acts transitively as permutation groups of automorphisms. In particular, we show that these codes are invariant under the 3-fold covers 3̂M22 and 3̂M22:2, respectively, of the Mathieu groups M22 and M22:2. Employing a known construction of strongly regular graphs from projective two-weight codes we obtain from the binary projective (respectively, quaternary projective) two-weight codes with parameters those given above, the strongly regular graphs with parameters (4096, 693, 152, 110), (4096, 1386, 482, 462), and (4096, 2016, 992, 992), respectively. The latter graph can be viewed as a 2-(4096, 2016, 992)-symmetric design with the symmetric difference property whose residual and derived designs with respect to a block give rise to binary self-complementary codes meeting the Grey–Rankin bound with equality. [ABSTRACT FROM AUTHOR]

A graph is ℓ -reconstructible if it is determined by its multiset of induced subgraphs obtained by deleting ℓ vertices. For graphs with at least six vertices, we prove that all graphs in a family containing all strongly regular graphs and most 2-partially distance-regular graphs are 2-reconstructible. [ABSTRACT FROM AUTHOR]

For an incidence geometry G = (P , L , I) with a linear representation T 2 ∗ (K) , we apply WQH switching to construct a non-geometric graph Γ ′ cospectral with the line graph Γ of G . As an application, we show that for h ≥ 2 and 0 < m < h , there are strongly regular graphs with parameters (v , k , λ , μ) = (2 2 h (2 m + h + 2 m - 2 h) , 2 h (2 h + 1) (2 m - 1) , 2 h (2 m + 1 - 3) , 2 h (2 m - 1)) which are not point graphs of partial geometries of order (s , t , α) = ((2 h + 1) (2 m - 1) , 2 h - 1 , 2 m - 1) . [ABSTRACT FROM AUTHOR]

Linear codes with complementary duals, shortly named LCD codes, are linear codes whose intersection with their duals is trivial. In this paper, we outline a construction for LCD codes over finite fields from the adjacency matrices of two-class association schemes. These schemes consist of either strongly regular graphs (SRGs) or doubly regular tournaments (DRTs). Under certain conditions, the method yields formally self-dual codes. Further, we propose a decoding algorithm that can be feasible for the LCD codes obtained using one of the given methods. [ABSTRACT FROM AUTHOR]

This paper provides new observations on the Lovász θ -function of graphs. These include a simple closed-form expression of that function for all strongly regular graphs, together with upper and lower bounds on that function for all regular graphs. These bounds are expressed in terms of the second-largest and smallest eigenvalues of the adjacency matrix of the regular graph, together with sufficient conditions for equalities (the upper bound is due to Lovász, followed by a new sufficient condition for its tightness). These results are shown to be useful in many ways, leading to the determination of the exact value of the Shannon capacity of various graphs, eigenvalue inequalities, and bounds on the clique and chromatic numbers of graphs. Since the Lovász θ -function factorizes for the strong product of graphs, the results are also particularly useful for parameters of strong products or strong powers of graphs. Bounds on the smallest and second-largest eigenvalues of strong products of regular graphs are consequently derived, expressed as functions of the Lovász θ -function (or the smallest eigenvalue) of each factor. The resulting lower bound on the second-largest eigenvalue of a k-fold strong power of a regular graph is compared to the Alon–Boppana bound; under a certain condition, the new bound is superior in its exponential growth rate (in k). Lower bounds on the chromatic number of strong products of graphs are expressed in terms of the order and the Lovász θ -function of each factor. The utility of these bounds is exemplified, leading in some cases to an exact determination of the chromatic numbers of strong products or strong powers of graphs. The present research paper is aimed to have tutorial value as well. [ABSTRACT FROM AUTHOR]

All regular two-graphs having up to 36 vertices are known, and the first open case is the enumeration of two-graphs on 38 vertices. It is known that there are at least 191 regular two-graphs on 38 vertices and at least 18 regular two-graphs on 42 vertices. The number of descendants of these two-graphs is 6760 and 120, respectively. In this paper, we classify strongly regular graphs with parameters (41, 20, 9, 10) having nontrivial automorphisms and show that there are exactly 7152 such graphs. We enumerate all regular two-graphs on 38 and 42 vertices with at least one descendant whose full automorphism group is nontrivial and establish that there are at least 194 regular two-graphs on 38 vertices and at least 752 regular two-graphs on 42 vertices. Furthermore, we construct descendants with a trivial automorphism group of the newly constructed two-graphs and increase the number of known strongly regular graphs with parameters (37, 18, 8, 9) and (41, 20, 9, 10) to 6802 and 18439m respectively. This significantly increases the number of known strongly regular graphs with parameters (41, 20, 9, 10). [ABSTRACT FROM AUTHOR]

In this paper, inspired by the work of Tan et al. (2010) [36] , Chee et al. (2011) [11] and Hyun et al. (2020) [19] , we propose two new constructions of strongly regular graphs on finite fields by using weakly regular bent functions, which generalize the results in the existing references. We obtain two families of strongly regular graphs with flexible parameters. We are also able to obtain a 3-class amorphic association scheme. Moreover, we show that many of the strongly regular graphs which we construct are Ramanujan graphs. [ABSTRACT FROM AUTHOR]

We classify small partial geometric designs (PGDs) by spectral characteristics of their concurrence matrices. It is well known that the concurrence matrix of a PGD can have at most three distinct eigenvalues, all of which are nonnegative integers. The matrix contains useful information on the incidence structure of the design. An ordinary 2‐(v,k,λ) $(v,k,\lambda)$ design has a single concurrence λ $\lambda $, and its concurrence matrix is circulant, a partial geometry has two concurrences 1 and 0, and a transversal design TDλ(k,u) ${\text{TD}}_{\lambda }(k,u)$ has two concurrences λ $\lambda $ and 0, and its concurrence matrix is circulant. In this paper, we survey the known PGDs by highlighting their concurrences and constructions. Then we investigate which symmetric circulant matrices are realized as the concurrence matrices of PGDs. In particular, we try to give a list of all PGDs of order up to 12 each of which has a circulant concurrence matrix. We then describe these designs along with their combinatorial properties and constructions. This work is part of the second author's Ph.D. dissertation [46]. [ABSTRACT FROM AUTHOR]

A quasi-strongly regular graph G of grade 2 with parameters (n , k , a ; c 1 , c 2) is a k -regular graph on n vertices such that every pair of adjacent vertices have a common neighbors, every pair of distinct nonadjacent vertices have c 1 or c 2 common neighbors, and for each c i (i = 1 , 2) , there exists a pair of non-adjacent vertices sharing c i common neighbors. The children G 1 and G 2 of the graph G are defined on the vertex set of G such that every two distinct vertices are adjacent in G 1 or G 2 if and only if they share c 1 or c 2 neighbors, respectively. The graph G is a quasi-strongly regular graph of type A or B if it is of grade 2 and has a child that is a connected strongly regular graph or a disjoint union of cliques of order m (m > 1) , respectively. In this paper, we investigate the spectral properties of the graph G if it is a quasi-strongly regular graph of type A or B. Several examples of distance-regular graphs which are quasi-strongly regular graphs of type A are given. Moreover, we give several constructions of quasi-strongly regular graphs and calculate their spectrum. [ABSTRACT FROM AUTHOR]

We investigate fat projective linear codes over ${\mathbb Z}_{p^{m}}$ , $m\geqslant 2$ , with two nonzero homogeneous weights (“two-weight codes”), building on the graph theory approach developed by Delsarte for codes over fields. Our main result is the classification of such codes under the additional assumption that the columns of a generator matrix of the code determine a cap in the projective Hjelmslev geometry $\mathop {\mathrm {PHG}}\nolimits (k-1, {\mathbb Z}_{p^{m}})$. This generalizes a result on projective two weight codes with dual distance at least four (Calderbank, 1982). The proof relies on a careful analysis of a certain strongly regular graph built on the cosets of the dual code, and on an interpretation of its parameters in terms of projective Hjelmslev geometry. [ABSTRACT FROM AUTHOR]

A strongly regular decomposition of a strongly reg- ular graph is a partition of the vertex set into two parts on which the induced subgraphs are strongly regular, or cliques or cocliques. Strongly regular designs (srd's) as defined by D. G. Higman are co- herent configurations of rank 10 with two fibers in which the homogeneous configuration on each fiber is a strongly regular graph. Haemers and Higman proved the equivalence between strongly regular decompositions, excluding special cases, and srd's with certain parameter conditions. Here we obtain this result by examining the srd's that admit a fusion to a strongly regular graph on the full vertex set. We derive equivalent conditions to Theorem 2.8 of Haemers and Higman by elementary methods. In- corporating recent works of Hanaki and Klin and Reichard, a table of feasible parameter sets for this class of srd's is presented along with a discussion of known constructions. In two cases, nonexistence is observed due to nonexistence of the strongly regular graph obtained through fusion. One of these is also ruled out by Hobart's generalized Krein conditions, applied to srd's. As strongly regular decompositions of the complete graph have sparked interest with recent papers we observe that in our situation this occurs only when the constituent graphs are also complete and the design is trivial. [ABSTRACT FROM AUTHOR]

In this paper, we study a class of linear codes defined by characteristic functions of certain subsets of a finite field. We derive a sufficient and necessary condition for such a code to be a minimal linear code by a character-theoretical approach. We obtain new three-weight or four-weight minimal linear codes that do not satisfy the Ashikhmin-Barg condition by using partial difference sets. We show that our construction yields minimal linear codes that do not arise from cutting vectorial blocking sets, and also discuss their applications in secret sharing schemes. [ABSTRACT FROM AUTHOR]

We say that a regular graph G of order n and degree r ≥ 1 (which is not the complete graph) is strongly regular if there exist non-negative integers τ and θ such that |Si ∩ Sj | = τ for any two adjacent vertices i and j, and |Si ∩ Sj | = θ for any two distinct non-adjacent vertices i and j, where Sk denotes the neighborhood of the vertex k. Let λ1 = r, λ2 and λ3 be the distinct eigenvalues of a connected strongly regular graph. Let m1 = 1, m2 and m3 denote the multiplicity of r, λ2 and λ3, respectively. We here describe the parameters n, r, τ and θ for strongly regular graphs with m2 = qm3 and m3 = qm2 for q = 3/2, 4/3, 5/2, 5/3, 5/4, 6/5. [ABSTRACT FROM AUTHOR]

Linear codes are widely studied due to their important applications in authentication codes, association schemes and strongly regular graphs, etc. In this paper, a class of at most three-weight linear codes is constructed by selecting a new defining set, then the parameters and weight distributions of codes are determined by exponential sums. Results show that almost all the linear codes we constructed are minimal and we also describe the access structures of the secret sharing schemes based on their dual. Especially, the new binary code is a two-weight projective code and based on which a strongly regular graph with new parameters is designed. [ABSTRACT FROM AUTHOR]

Modular strongly regular graphs have been introduced by Greaves et al. (Linear Algebra Appl 639:50–80, 2022). We show that a related class of isodual codes is asymptotically good. Equiangular tight frames over finite fields also introduced by the same authors in 2022 are shown here to connect with self-dual codes. We give several examples of equiangular tight frames over finite fields arising from self-dual codes. [ABSTRACT FROM AUTHOR]

In this paper we consider strongly regular graphs G which admit a decomposition into two strongly regular graphs such that one of them, say H, is a star complement of G. Relations between the parameters of graphs paired in this way are determined. We also consider several particular types of strongly regular graph and determine whether such graphs can appear in the role of G or H. [ABSTRACT FROM AUTHOR]

A Deza graph with parameters (v,k,b,a) is a k‐regular graph on v vertices in which the number of common neighbors of two distinct vertices takes one of the following values: b or a, where b≥a. In the previous papers Deza graphs with b=k−1 were characterized. In this paper, we characterize Deza graphs with b=k−2. [ABSTRACT FROM AUTHOR]

In 2018 the first, Rukavina and the third author constructed with the aid of a computer the first example of a strongly regular graph Γ with parameters (216, 40, 4, 8) and proved that it is the unique PSU (4 , 2) -invariant vertex-transitive graph on 216 vertices. In this paper, using the geometry of the Hermitian surface of PG (3 , 4) , we provide a computer-free proof of the existence of the graph Γ . The maximal cliques of Γ are also determined. [ABSTRACT FROM AUTHOR]

We investigate the problem of finding all the biregular graphs with just three adjacency eigenvalues, one of which is an eigenvalue ≠ − 1 , 0 of maximal possible multiplicity. [ABSTRACT FROM AUTHOR]

In this paper, we consider regular automorphism groups of graphs in the RT2 family and the Davis‐Xiang family and amorphic abelian Cayley schemes from these graphs. We derive general results on the existence of non‐abelian regular automorphism groups from abelian regular automorphism groups and apply them to the RT2 family and Davis‐Xiang family and their amorphic abelian Cayley schemes to produce amorphic non‐abelian Cayley schemes. [ABSTRACT FROM AUTHOR]

Partial difference sets with parameters (v,k,λ,μ)=(v,(v−1)/2,(v−5)/4,(v−1)/4) are called Paley type partial difference sets. In this note, we prove that if there exists a Paley type partial difference set in an abelian group of order v, where v is not a prime power, then v=n4 or 9n4, n>1 an odd integer. In 2010, Polhill constructed Paley type partial difference sets in abelian groups with those orders. Thus, combining with the constructions of Polhill and the classical Paley construction using nonzero squares of a finite field, we completely answer the following question: "For which odd positive integers v>1, can we find a Paley type partial difference set in an abelian group of order v?" [ABSTRACT FROM AUTHOR]

Koolen et al. showed that if a connected graph with smallest eigenvalue at least - 3 has large minimal valency, then it is 2-integrable. In this paper, we will prove that a lower bound for the minimal valency is 166. [ABSTRACT FROM AUTHOR]

We show that the strongly regular graph on non-isotropic points of one type of the polar spaces of type U (n , 2) , O (n , 3) , O (n , 5) , O + (n , 3) , and O − (n , 3) are not determined by its parameters for n ≥ 6. We prove this by using a variation of Godsil-McKay switching recently described by Wang, Qiu, and Hu. This also results in a new, shorter proof of a previous result of the first author which showed that the collinearity graph of a polar space is not determined by its spectrum. The same switching gives a linear algebra explanation for the construction of a large number of non-isomorphic designs. [ABSTRACT FROM AUTHOR]

A two‐character set in PG(r,q) is a set X of points with the property that the intersection number with any hyperplane only takes two values. A projective Paley set of PG(2n−1,q),q odd, is a subset X of points such that every hyperplane of PG(2n−1,q) meets X in either (qn+1)(qn−1−1)∕2(q−1) or (qn−1)(qn−1+1)∕2(q−1) points. A quasi‐quadric in PG(2n−1,q) is a two‐character set that has the same size and the same intersection numbers with respect to hyperplanes as a nondegenerate quadric. Here we construct projective Paley sets of PG(3,q) left invariant by a cyclic group of order q2+1 and of PG(5,q) admitting PSL(2,q2) as an automorphism group. Also infinite families of quasi‐quadrics of PG(5,q) are provided. [ABSTRACT FROM AUTHOR]

We study the behavior of the 2-rank of the adjacency matrix of a graph under Seidel and Godsil–McKay switching, and apply the result to graphs coming from graphical Hadamard matrices of order 4 m. Starting with graphs from known Hadamard matrices of order 64, we find (by computer) many Godsil–McKay switching sets that increase the 2-rank. Thus we find strongly regular graphs with parameters (63 , 32 , 16 , 16) , (64 , 36 , 20 , 20) , and (64 , 28 , 12 , 12) for almost all feasible 2-ranks. In addition we work out the behavior of the 2-rank for a graph product related to the Kronecker product for Hadamard matrices, which enables us to find many graphical Hadamard matrices of order 4 m for which the number of related strongly regular graphs with different 2-ranks is unbounded as a function of m. The paper extends results from the article 'Switched symplectic graphs and their 2-ranks' by the first and the last author. [ABSTRACT FROM AUTHOR]

In this paper we construct transitive t-designs from the linear groups L(2, q), q ≤ 23. Thereby we classify t-designs, t ≥ 2, admitting a transitive action of the linear groups L(2, q), q ≤ 23, up to 35 points and obtained numerous transitive designs, for 36 ≤ v ≤ 55. In many cases we proved the existence of t-designs with certain parameter sets. Among others we constructed t-designs with parameters 2-(55, 10, 4), 3-(24, 11, 495), 3-(24, 12, 5m), m 2 f11, 12, 22, 33, 44, 66, 132g. Furthermore, we constructed strongly regular graphs admitting a transitive action of the linear groups L(2, q), q ≤ 23. [ABSTRACT FROM AUTHOR]

In this paper we investigate bounds on set multipartite Ramsey numbers for the bipartite graph K 2 , n , extending or improving well-known upper bounds by Chung and Graham, Irving, Lortz and Mengersen. Known constructions based on certain classes of combinatorial designs (projective plane, Hadamard matrix, strongly regular graph) yield near-optimal bounds. As the main goal, a new construction based on strongly regular graph and Hadamard matrix produces a sharp class, generalizing a classical bound by Exoo, Harborth, and Mengersen. [ABSTRACT FROM AUTHOR]

We present a new non-existence proof for the strongly regular graph G with parameters (76, 21, 2, 7), using the unit vector representation of the graph. [ABSTRACT FROM AUTHOR]

A quasi-strongly regular graph of grade 2 with parameters (n , k , a ; c 1 , c 2) is a k -regular graph on n vertices such that every pair of adjacent vertices have a common neighbours, every pair of distinct nonadjacent vertices have c 1 or c 2 common neighbours, and for each c i (i = 1 , 2) , there exists a pair of non-adjacent vertices sharing c i common neighbours. If a quasi-strongly regular graph is neither a strongly regular graph nor a Deza graph, then it is called a strictly quasi-strongly regular graph. In earlier papers, we characterised the strictly quasi-strongly regular graphs with parameters (n , k , a ; k − 2 , c 2) satisfying a ≥ k − 5. In this paper, we characterize strictly quasi-strongly regular graphs with parameters (n , k , a ; k − 2 , c 2) satisfying a < k − 5 and l 1 > 2 , where l 1 is the number of vertices with k − 2 common neighbours with a given vertex. [ABSTRACT FROM AUTHOR]

Abstract Let Q − (2 n + 1 , q) be an elliptic quadric of PG (2 n + 1 , q). A relative m -ovoid of Q − (2 n + 1 , q) (with respect to a parabolic section Q ≔ Q (2 n , q) ⊂ Q − (2 n + 1 , q)) is a subset R of points of Q − (2 n + 1 , q) ∖ Q such that every generator of Q − (2 n + 1 , q) not contained in Q meets R in precisely m points. A relative m -ovoid having the same size as its complement (in Q − (2 n + 1 , q) ∖ Q) is called a relative hemisystem. We show that a nontrivial relative m -ovoid of Q − (2 n + 1 , q) is necessarily a relative hemisystem, forcing q to be even. Also, we construct an infinite family of relative hemisystems of Q − (4 n + 1 , q) , n ≥ 2 , admitting PSp (2 n , q 2) as an automorphism group. Finally, some applications are given. [ABSTRACT FROM AUTHOR]

Abstract Highly regular graphs for which not all regularities are explainable by symmetries are fascinating creatures. Some of them like, e.g., the line graph of W. Kantor's non-classical GQ (5 2 , 5) , are stumbling stones for existing implementations of graph isomorphism tests. They appear to be extremely rare and even once constructed it is difficult to prove their high regularity. Yet some of them, like the McLaughlin graph on 275 vertices and Ivanov's graph on 256 vertices are of profound beauty. This alone makes it an attractive goal to strive for their complete classification or, failing this, at least to get a deep understanding of them. Recently, one of the authors discovered new methods for proving high regularity of graphs. Using these techniques, in this paper we study a classical family of strongly regular graphs, originally discovered by A.E. Brouwer, A.V. Ivanov, and M.H. Klin in the late 80s. We analyse their symmetries and show that they are (3 , 5) -regular but not 2-homogeneous. Thus we promote these graphs to the distinguished club of highly regular graphs with few symmetries. [ABSTRACT FROM AUTHOR]

Let G be a connected graph. An edge cut set M of G is a cyclic edge cut set if there are at least two components of G - M which contain a cycle. The cyclic edge-connectivity of G is the minimum cardinality of a cyclic edge cut set (if exists) of G. In this paper, we show that the cyclic edge-connectivity of a connected strongly regular graph G (not K 3 , 3 ) of degree k ≥ 3 with girth c is equal to (k - 2) c , where c = 3 , 4 or 5. Moreover, if G is not the triangular graph srg-(10, 6, 3, 4), the complete multi-partite graph K 2 , 2 , 2 , 2 or the lattice graph srg-(16, 6, 2, 2), then each cyclic edge cut set of size (k - 2) c is precisely the set of edges incident with a cycle of length c in G. [ABSTRACT FROM AUTHOR]

A Deza graph with parameters (n,k,b,a) is a k‐regular graph with n vertices, in which any two vertices have a or b (a≤b) common neighbours. A Deza graph is strictly Deza if it has diameter 2, and is not strongly regular. In an earlier paper, the two last authors et al characterised the strictly Deza graphs with b=k−1 and β>1, where β is the number of vertices with b common neighbours with a given vertex. Here, we start with a characterisation of Deza graphs (not necessarily strictly Deza graphs) with parameters (n,k,k−1,0). Then, we deal with the case β=1 and a>0, and thus complete the characterisation of Deza graphs with b=k−1. It follows that all Deza graphs with b=k−1, β=1 and a>0 can be made from special strongly regular graphs, and in fact are strictly Deza except for K2. We present several examples of such strongly regular graphs. A divisible design graph (DDG) is a special Deza graph, and a Deza graph with β=1 is a DDG. The present characterisation reveals an error in a paper on DDGs by the second author et al. We discuss the cause and the consequences of this mistake and give the required errata. [ABSTRACT FROM AUTHOR]

Abstract Balancedly splittable Hadamard matrices are introduced and studied. A connection is made to the Hadamard diagonalizable strongly regular graphs, maximal equiangular lines set, and unbiased Hadamard matrices. Several construction methods are presented. As an application, commutative association schemes of 4, 5, and 6 classes are constructed. [ABSTRACT FROM AUTHOR]

A $p$ -ary function $f$ in $n$ variables is an $l$ - form if $f({\mathrm{ tu}})=t^{l}f(u)$ for any nonzero $t$ in $\mathbb {Z}_{p}$ and $u$ in $\mathbb {Z}^{n}_{p}$. Let $n$ be a positive even integer, $p$ an odd prime, and $l$ an element of $\{1,2,\ldots ,p-1\}$ provided that $l \neq p-1$ if $p>3$. Let $f$ be a $p$ -ary bent function in $n$ variables of $l$ -form with $f(0)=0$ and $\gcd (l-1,p-1)=1$ , and let $H_{l}=\{t^{l}:t\in \mathbb {Z}^{*}_{p}\}$. We denote by $G_{f,l}$ the Cayley graph ${\mathrm {Cay}} (\mathbb {Z}^{n}_{p},\cup _{s\in H_{l}}f^{-1}(s))$. Our main results are as follows: 1) if there is weakly regular $p$ -ary bent $f$ which is not regular, then $l$ is 2; 2) if $l=2$ , then $f$ is weakly regular $p$ -ary bent if and only if the Cayley graph $G_{f,l}$ is strongly regular; 3) if $l\neq 2$ , then $f$ is regular $p$ -ary bent if and only if the Cayley graph $G_{f,l}$ is strongly regular; 4) $G_{f,l}$ can be replaced by ${\mathrm {Cay}} (\mathbb {Z}^{n}_{p},f^{-1}(0)\setminus \{0\})$ in 2) and 3); and 5) amorphic association schemes are derived by using 2) and 3). We prove our main results by computing at most four distinct restricted eigenvalues of $G_{f,l}$. [ABSTRACT FROM AUTHOR]

We prove the existence of strongly regular graphs with parameters (216, 40, 4, 8) and (540, 187, 58, 68). We also construct a strongly regular graph with parameters (540, 224, 88, 96) that was previously unknown. Further, we construct all distance-regular graphs with at most 600 vertices, admitting a transitive action of the orthogonal group O + ( 6 , 2 ) or O − ( 6 , 2 ) . Furthermore, we show that under certain conditions an orbit matrix M of a strongly regular graph Γ can be used to define a new strongly regular graph Γ ˜ , where the vertices of the graph Γ ˜ correspond to the orbits of Γ (the rows of M ). We show that some of the obtained strongly regular graphs are related to each other in a way that one can be constructed from an orbit matrix of the other. [ABSTRACT FROM AUTHOR]

A generalized strongly regular graph of grade p, as a generalization of strongly regular graphs, is a regular graph such that the number of common neighbours of both any two adjacent vertices and any two non-adjacent vertices takes on p distinct values. In this paper, we study generalized strongly regular graphs of grade 2 and provide some inequalities for the eigenvalues of them. In particular, we investigate a special family of generalized strongly regular graphs of grade 2, i.e., semi-strongly regular graphs. We obtain a relation between the parameters and two inequalities for the eigenvalues of these graphs. We also present some constructions of generalized strongly regular graphs based on Cayley graphs, graph operations and association schemes, respectively. [ABSTRACT FROM AUTHOR]

We exhibit a new construction of edge-regular graphs with regular cliques that are not strongly regular. The infinite family of graphs resulting from this construction includes an edge-regular graph with parameters (24 , 8 , 2). We also show that edge-regular graphs with 1-regular cliques that are not strongly regular must have at least 24 vertices. [ABSTRACT FROM AUTHOR]

When association schemes are viewed as a generalization of groups, it becomes natural to seek non-commutative examples. As with groups, non-commutative association schemes must have at least six elements, but unlike in group theory, there are numerous examples with exactly six elements. One method to try to classify such schemes is to attempt to construct extensions of schemes of rank 3, starting with those schemes of rank 3 which correspond to self-complementary strongly regular graphs with a vertex-transitive automorphism group. Recent work of Klin, Kriger, and Woldar provides new constructions for such graphs. In this paper, we investigate the possibility of constructing new non-commutative schemes with six elements from these graphs. [ABSTRACT FROM AUTHOR]

Abstract: We investigate strongly regular graphs for which Hoffman's ratio bound and Cvetcović's inertia bound are equal. This means that v e − = m − ( e − − k ), where v is the number of vertices, k is the regularity, e − is the smallest eigenvalue, and m − is the multiplicity of e −. We show that Delsarte cocliques do not exist for all Taylor's 2‐graphs and for point graphs of generalized quadrangles of order ( q , q 2 − q ) for infinitely many q. For cases where equality may hold, we show that for nearly all parameter sets, there are at most two Delsarte cocliques. [ABSTRACT FROM AUTHOR]

A binary [98280,24,47104]2 projective two-weight code related to the sporadic simple group Co1 of Conway is constructed as a faithful and absolutely irreducible submodule of the permutation module induced by the primitive action of Co1 on the cosets of Co2. The dual code of this code is a uniformly packed [98280,98256,3]2 code. The geometric significance of the codewords of the code can be traced to the vectors in the Leech lattice, thus revealing that the stabilizer of any non-zero weight codeword in the code is a maximal subgroup of Co1. Similarly, the stabilizer of the codewords of minimum weight in the dual code is a maximal subgroup of Co1. As by-product, a new strongly regular graph on 16777216 vertices and valency 98280 is constructed using the codewords of the code. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

An equiangular tight frame (ETF) is a set of unit vectors whose coherence achieves the Welch bound, and so is as incoherent as possible. Though they arise in many applications, only a few methods for constructing them are known. Motivated by the connection between real ETFs and graph theory, we introduce the notion of ETFs that are symmetric about their centroid. We then discuss how well-known constructions, such as harmonic ETFs and Steiner ETFs, can have centroidal symmetry. Finally, we establish a new equivalence between centroid-symmetric real ETFs and certain types of strongly regular graphs (SRGs). Together, these results give the first proof of the existence of certain SRGs, as well as the disproofs of the existence of others. [ABSTRACT FROM AUTHOR]