Designs over edge-regular, co-edge-regular and amply regular graphs are investigated. Using linear algebra, we obtain lower bounds in certain inequalities involving the parameters of the designs. ...Some results on designs meeting the bounds are obtained. These designs are over connected regular graphs with least eigenvalue
-
2
, have the minimal number of blocks and do not appear in an earlier work. Partial classification such designs over strongly regular graphs with least eigenvalue
-
2
is given.
An undirected graph with
v
vertices in which the degrees of all vertices are equal to
k
, each edge is contained in exactly
λ
triangles, and the intersection of the neighborhoods of any two vertices ...at distance 2 contains exactly µ vertices is called amply regular with parameters (
v, k, λ
, µ). We complete the classification of amply regular graphs with
b
1
= 6, where
b
1
=
k
−
λ
− 1.
The concept of intersection numbers of order
r for
t-designs is generalized to graphs and to block designs which are not necessarily
t-designs. These intersection numbers satisfy certain integer ...linear equations involving binomial coefficients, and information on the non-negative integer solutions to these equations can be obtained using the block intersection polynomials introduced by P.J. Cameron and the present author. The theory of block intersection polynomials is extended, and new applications of these polynomials to the studies of graphs and block designs are obtained. In particular, we obtain a new method of bounding the size of a clique in an edge-regular graph with given parameters, which can improve on the Hoffman bound when applicable, and a new method for studying the possibility of a graph with given vertex-degree sequence being an induced subgraph of a strongly regular graph with given parameters.
The connected components of the induced graphs on each subconstituent of the dual polar graph of the odd dimensional orthogonal spaces over a finite field are shown to be amply regular. The connected ...components of the graphs on the second and third subconstituents are shown to be distance-regular by elementary methods.
The study of distance-regular graphs in which neighborhoods of vertices are strongly regular graphs with eigenvalue 3 was initiated by Makhnev. In particular, he reduced these graphs to graphs in ...which neighborhoods of vertices are exceptional graphs or pseudogeometric graphs for
pG
s
−3
(
s
,
t
). Makhnev and Paduchikh found parameters of exceptional graphs (see the proposition). In the present paper, we study amply regular graphs in which neighborhoods of vertices are exceptional strongly regular graphs with nonprincipal eigenvalue 3 and parameters from conditions 3–6 of the Proposition.
Amply regular graphs with Hoffman’s condition Kabanov, V. V.; Unegov, S. V.
Proceedings of the Steklov Institute of Mathematics,
07/2009, Letnik:
264, Številka:
Suppl 1
Journal Article
Recenzirano
It is known that, if the minimal eigenvalue of a graph is −2, then the graph satisfies Hoffman’s condition: for any generated complete bipartite subgraph
K
1,3
(a 3-claw) with parts {
p
} and {
q
1
,
...q
2
,
q
3
}, any vertex distinct from
p
and adjacent to the vertices
q
1
and
q
2
is adjacent to
p
but not adjacent to
q
3
. We prove the converse statement for amply regular graphs containing a 3-claw and satisfying the condition µ > 1.
PDF
