An infinite sequence of ΓΔ-regular graphs

✍ Scribed by T. Kloks

• Publisher: Elsevier Science
• Year: 1988
• Tongue: English
• Weight: 494 KB
• Volume: 73
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(88)90140-9

✦ Synopsis

In this paper we are interested in graphs which, in a sense, are a generalization of strongly regular graphs. We remind the reader that a strongly regular graph with parameters n, k, A, p (notation SRG(n, k, A, p)) is a graph on it vertices, regular of degree k, and such that any two vertices joined, resp. not joined, by an edge have il, resp. cc, common neighbours. If G is a graph and x a vertex of 6, then r(x) will denote the se! of neighbours of x and also the induced subgraph on these vertices. Similarly with A(x) for the non-neighbours. So, in an SRG(n, k, il, p) both r(c) and A(x) are regular subgraphs (with degree II, resp. k -p). The following problem was suggested by Seidel. Study the class of graphs with the property that T(X) and A(x) are regular for every vertex x of G. Notice that no requirement is made about the degree of the subgraphs T(x) and We call such a graph G a neighbourhood-regular graph or rd-regular graph. In 1979 these graphs were studied by Godsil and McKay [2]. To give the reader some feeling for the problem we briefly survey their most important results.

If G is connected and r(x) is regular for c fry x E G, then there is a number a such that each r(x) has degree A.