Construction of a Strongly Regular Graph which has regular Neighbourhood graphs in all iteration.

Question

Notation and Definition: $G$ is a Strongly Regular Graph (not complete or a cycle) and is denoted by $\mathrm{SRG}(n,r, \lambda, \mu)$ if it has the following properties:

1. Every two adjacent vertices have $\lambda$ common neighbors.
2. Every two non-adjacent vertices have $\mu$ common neighbors.
3. $r$-regular and total $n$ vertices.

Let $x_1\in V(G)$. Let $C_1$ be the subgraph of $G$ induced by all vertices not adjacent to $x_1$. Let $D_1$ be the subgraph of $G$ induced by all vertices adjacent to $x_1$ create a sub-graph $D_1$.

Let $x_2\in V(D_1)$. Using same method, based on adjacency of $x_2$, $D_1$ can be divided into induced subgraphs. Let $C_2$ be the subgraph of $D_1$ induced by all vertices not adjacent to $x_2$. Let $D_2$ be the subgraph of $D_1$ induced by all vertices adjacent to $x_2$.

In general, $D_y $ can be divided into 2 subgraphs $C_{y+1}$ and $D_{y+1}$.

Problems:

1. Find a relation in terms of $n,r, \lambda, \mu$ such that the graphs having this relation always have $C_y$, $D_y$ as $s_y$-, $t_y$-regular graphs, respectively, for all iterations $y$ where $s_y,t_y>0$ and $s_y \neq t_y$.

2. Find a relation in terms of $n,r, \lambda, \mu $ so that the graphs having this relation always have $D_y$ as a $ t_y$-regular graph for all iterations $y$ where $t_y>0$.

Note: $C_y, D_y$ are not complete graphs.

How can I find such class of graph or how can I determine such formula in terms of $n,r, \lambda, \mu $?

Motivation : An algorithm runs faster than existing results for this kind of graphs.

Attempt:

$G$ is a strongly regular graph with parameter $(n,r,\lambda, \mu)$ . $x_1 \in G$. All vertices adjacent to $x_1$ create a set $D_1$ and all non adjacent to $x_1$ create a set $C_1$. Consider the graph $(G- x_1 -V(C_1) ) $ where $ V(C_1) $ has all vertices of set $C_1$. the graph $(G-{x_1}-V(C_1))=$ induced subgraph $D_1$ of $G$.

Note that, each vertex of $D_1$ lost constant number of edges and vertices. When It was in $G$, each vertex had $( r,\lambda, \mu)$ parameters. Constant number of deletion of edges and vertices, will decrease parameters at a constant rate , so in induced subgraph $D_1$, parameters will be $(n-a,r-b,\lambda-c , \mu-d)$ , which makes the graph a strongly regular graph .

otherwise $D_1$ is a cycle graph.

If $D_1$ is a Strongly Regular Graph , then same way, $D_2$ will be a Strongly Regular Graph. This argument will continue until

1. $D_k$ is a cycle graph where $k\leq y$.
2. $t_y- t_{y+1} \leq \lambda_y$

Related Papers :

1. V.A.Taskinov. Regular subgraphs of regular graphs. Sov.Math.Dokl.26(1982), 37-38 . In this paper he proved the following : Let $0<k<r$ be positive odd integers. Then every $r$-regular graph contains a $k$-regular subgraph (Here, the graph need not be simple).

2. N. ALON,S. FRIEDLAND,G. KALAI. Regular Subgraphs of Almost Regular Graphs. JOURNAL OF COMBINATORIAL THEORY, Series B 37, 79-91 (1984)

Answer 1

Okay, so you have $G$ a $srg(n,r,\lambda,\mu)$, $D_{1}$ is the neighborhood graph of a vertex $x_{1}$ (I'm assuming $x_{1}$ is NOT in $D_{1}$); then you take $x_{2}$ in $D_{1}$, and create $D_{2}$ which is the intersection of the two neighborhoods. So $D_{1}$ will contain $r$ vertices, and since each two adjacent vertices share $\lambda$ common neighbors, $D_{1}$ will be $\lambda$-regular (NOTE: There is no guarantee $D_{1}$ will be strongly regular, in fact there are many counterexamples, $T(6)$ for instance). Then $D_{2}$ (determined by $x_{2}$) will contain $\lambda$ vertices. What do we need to have happen for $D_{2}$ to be regular?

This is how I would start the problem. I can't say for sure how to proceed from here. I think it would help to make very clear what your conjecture is before trying to prove anything. For example, when does the process stop (ie what is $y$)? For statements like "$C_{y}$, $D_{y}$ are not complete graphs", "$D_{1}$ is strongly regular", etc, are these things you are claiming are always true, or are they assumptions you are making for the specific graphs you are interested in? What are your parameters, for example $a$,$b$,$c$,$d$? What are $t_{y}$, $t_{y+1}$? What is $\lambda_{y}$? What is $y$?

As mentioned in chat, $D_{1}$ is NOT always strongly regular or a cycle graph (see triangular graph $T(6)$). In the same way, $D_{1}$ being strongly regular is no guarantee that $D_{2}$ will be strongly regular.