Strongly Regular Vertices and Partially Strongly Regular Graphs

Abstract

A strongly regular vertex with parameters \((\lambda, \mu)\) in a graph is a vertex \(x\) such that the number of neighbors any other vertex \(y\) has in common with \(x\) is \(\lambda\) if \(y\) is adjacent to \(x\), and is \(\mu\) if \(y\) is not adjacent to \(x\). In this note, we will prove some basic properties of these vertices and the graphs that contain them, as well as provide some simple constructions of regular graphs that are not necessarily strongly regular, but do contain many strongly regular vertices. We also make several conjectures and find all regular graphs on at most ten vertices with at least one strongly regular vertex.