Search Results: 1 - 10 of 100 matches for " "
All listed articles are free for downloading (OA Articles)
Page 1 /100
Display every page Item
There is no strongly regular graph with parameters (460,153,32,60)  [PDF]
A. V. Bondarenko,A. Mellit,A. Prymak,D. Radchenko,M. Viazovska
Mathematics , 2015,
Abstract: We prove that there is no strongly regular graph (SRG) with parameters (460,153,32,60). The proof is based on a recent lower bound on the number of 4-cliques in a SRG and some applications of Euclidean representation of SRGs.
There is no (75,32,10,16) strongly regular graph  [PDF]
Jernej Azarija,Tilen Marc
Mathematics , 2015,
Abstract: We show that there is no (75,32,10,16) strongly regular graph. The result is obtained by a mix of algebraic and computational approaches. The main idea is to build large enough induced structure and apply the star complement technique. Our result implies that there is no regular two-graph on 76 vertices and no partial geometry with parameters pg(4,7,2). In particular, it implies that there is no (76,35,18,14) strongly-regular graph. In order to solve this classification problem we also develop an efficient algorithm for the problem of finding a maximal clique in a graph.
Non-existence of (76,30,8,14) strongly regular graph and some structural tools  [PDF]
A. V. Bondarenko,A. Prymak,D. Radchenko
Mathematics , 2014,
Abstract: Our main result is the non-existence of strongly regular graph with parameters (76,30,8,14). We heavily use Euclidean representation of a strongly regular graph, and develop a number of tools that allow to establish certain structural properties of the graph. In particular, we give a new lower bound for the number of 4-cliques in a strongly regular graph.
Binomial Hadamard Series and Inequalities over the Spectra of a Strongly Regular Graph  [PDF]
Luís Vieira
Applied Mathematics (AM) , 2018, DOI: 10.4236/am.2018.99071
Let G be a primitive strongly regular graph of order n and A is adjacency matrix. In this paper we first associate to A a real 3-dimensional Euclidean Jordan algebra?\"\" with rank three spanned by In and the natural powers of A that is a subalgebra of the Euclidean Jordan algebra of symmetric matrix of order n. Next we consider a basis?\"\" that is a Jordan frame of \"\". Finally, by an algebraic asymptotic analysis of the second spectral decomposition of some Hadamard series associated to A we establish some inequalities over the spectra and over the parameters of a strongly regular graph.
Strongly Regular Graphs with No Triangles  [PDF]
Norman Biggs
Mathematics , 2009,
Abstract: A simplified version of the theory of strongly regular graphs is developed for the case in which the graphs have no triangles. This leads to (i) direct proofs of the Krein conditions, and (ii) the characterization of strongly regular graphs with no triangles such that the second subconstituent is also strongly regular. The method also provides an effective means of listing feasible parameters for such graphs.
New strongly regular graphs derived from the G2(4) graph  [PDF]
Thomas Jenrich
Mathematics , 2014,
Abstract: We consider simple loopless finite undirected graphs. Such a graph is called strongly regular with parameter set (v,k,l,m), for short a srg(v,k,l,m), iff it has exactly v vertices, each of them has exactly k neighbours, and the number of common neighbours of any two different vertices is l if they are neighbours and m otherwise. The G2(4) graph is a well-known srg(416,100,36,20). In this article, we explicitly construct it and a certain subgraph E induced by 320 vertices in the same way as in an older article by this author. We discover some interesting properties of E and derive two strongly regular graphs from it: A subgraph F induced by 256 vertices which is a srg(256,60,20,12), and a supergraph H which is a srg(336,80,28,16) and where E is an induced subgraph of H. While H seems to be completely unknown up to now, F is isomorphic to objects described as unions of 16 16-cocliques in a description of subgraphs of the G2(4) graph by Andries E. Brouwer; but the strong regularity has been unnoticed before. Several propositions in this article have been checked by executing the additionally (in the source package) provided program G24DGS and the program Dreadnaut from the popular graph theoretic software nauty (by Brendan McKay and Adolfo Piperno).
On a conjecture of Brouwer involving the connectivity of strongly regular graphs  [PDF]
Sebastian M. Cioaba,Kijung Kim,Jack H. Koolen
Computer Science , 2011, DOI: 10.1016/j.jcta.2012.01.001
Abstract: In this paper, we study a conjecture of Andries E. Brouwer from 1996 regarding the minimum number of vertices of a strongly regular graph whose removal disconnects the graph into non-singleton components. We show that strongly regular graphs constructed from copolar spaces and from the more general spaces called $\Delta$-spaces are counterexamples to Brouwer's Conjecture. Using J.I. Hall's characterization of finite reduced copolar spaces, we find that the triangular graphs $T(m)$, the symplectic graphs $Sp(2r,q)$ over the field $\mathbb{F}_q$ (for any $q$ prime power), and the strongly regular graphs constructed from the hyperbolic quadrics $O^{+}(2r,2)$ and from the elliptic quadrics $O^{-}(2r,2)$ over the field $\mathbb{F}_2$, respectively, are counterexamples to Brouwer's Conjecture. For each of these graphs, we determine precisely the minimum number of vertices whose removal disconnects the graph into non-singleton components. While we are not aware of an analogue of Hall's characterization theorem for $\Delta$-spaces, we show that complements of the point graphs of certain finite generalized quadrangles are point graphs of $\Delta$-spaces and thus, yield other counterexamples to Brouwer's Conjecture. We prove that Brouwer's Conjecture is true for many families of strongly regular graphs including the conference graphs, the generalized quadrangles $GQ(q,q)$ graphs, the lattice graphs, the Latin square graphs, the strongly regular graphs with smallest eigenvalue -2 (except the triangular graphs) and the primitive strongly regular graphs with at most 30 vertices except for few cases. We leave as an open problem determining the best general lower bound for the minimum size of a disconnecting set of vertices of a strongly regular graph, whose removal disconnects the graph into non-singleton components.
The asymptotics of strongly regular graphs  [PDF]
Vladimir Nikiforov
Mathematics , 2004,
Abstract: A strongly regular graph is called trivial if it or its complement is a union of disjoint cliques. We prove that every infinite family of nontrivial strongly regular graphs is quasi-random in the sense of Chung, Graham and Wilson.
Binary Representations of Regular Graphs  [PDF]
Yury J. Ionin
International Journal of Combinatorics , 2011, DOI: 10.1155/2011/101928
Abstract: For any 2-distance set in the n-dimensional binary Hamming space , let be the graph with as the vertex set and with two vertices adjacent if and only if the distance between them is the smaller of the two nonzero distances in . The binary spherical representation number of a graph , or bsr( ), is the least n such that is isomorphic to , where is a 2-distance set lying on a sphere in . It is shown that if is a connected regular graph, then bsr , where b is the order of and m is the multiplicity of the least eigenvalue of , and the case of equality is characterized. In particular, if is a connected strongly regular graph, then bsr if and only if is the block graph of a quasisymmetric 2-design. It is also shown that if a connected regular graph is cospectral with a line graph and has the same binary spherical representation number as this line graph, then it is a line graph. 1. Introduction The subject of this paper is mutual relations between regular and strongly regular graphs, 2-distance sets in binary Hamming spaces, and quasisymmetric 1- and 2-designs. The following relation between strongly regular graphs and 2-distance sets in Euclidean spaces is well known (cf. [1, Theorem 2.23]): if is the multiplicity of the least eigenvalue of a connected strongly regular graph of order , then the vertex set of can be represented as a set of points, lying on a sphere in , so that there exist positive real numbers such that the distance between any two distinct vertices is equal to if they are adjacent as vertices of and it is equal to otherwise. This result was recently generalized to all connected regular graphs in [2]. It has also been proved in [2] that, given and , such a representation of a connected regular graph in is not possible. The notion of a 2-distance set representing a graph makes sense for any metric space, and the spaces of choice in this paper are the binary Hamming spaces. We will show (Theorem 3.3) that the dimension of a binary Hamming space, in which a connected regular graph can be represented, is at least , where and have the same meaning as in the previous paragraph. It is also well known that the block graph of a quasisymmetric 2-design is strongly regular. However, many strongly regular graphs are not block graphs, and there is no good characterization of the graphs that are block graphs of quasisymmetric 2-designs. The situation changes if we consider the representation of graphs in binary Hamming spaces. We will show (Theorem 4.6) that a connected strongly regular graph admits a representation in the binary Hamming space of the
Strongly walk-regular graphs  [PDF]
Edwin R. van Dam,Gholamreza Omidi
Mathematics , 2012, DOI: 10.1016/j.jcta.2013.01.006
Abstract: We study a generalization of strongly regular graphs. We call a graph strongly walk-regular if there is an $\ell >1$ such that the number of walks of length $\ell$ from a vertex to another vertex depends only on whether the two vertices are the same, adjacent, or not adjacent. We will show that a strongly walk-regular graph must be an empty graph, a complete graph, a strongly regular graph, a disjoint union of complete bipartite graphs of the same size and isolated vertices, or a regular graph with four eigenvalues. Graphs from the first three families in this list are indeed strongly $\ell$-walk-regular for all $\ell$, whereas the graphs from the fourth family are $\ell$-walk-regular for every odd $\ell$. The case of regular graphs with four eigenvalues is the most interesting (and complicated) one. Such graphs cannot be strongly $\ell$-walk-regular for even $\ell$. We will characterize the case that regular four-eigenvalue graphs are strongly $\ell$-walk-regular for every odd $\ell$, in terms of the eigenvalues. There are several examples of infinite families of such graphs. We will show that every other regular four-eigenvalue graph can be strongly $\ell$-walk-regular for at most one $\ell$. There are several examples of infinite families of such graphs that are strongly 3-walk-regular. It however remains open whether there are any graphs that are strongly $\ell$-walk-regular for only one particular $\ell$ different from 3.
Page 1 /100
Display every page Item

Copyright © 2008-2017 Open Access Library. All rights reserved.