3
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ Probably ,1 and 2 both are same. $\endgroup$ – Jim Aug 5 '15 at 22:13
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ motivation : an isomorphism algorithm works better than existing result on this kind of graph. Attempt: i have tried to find out the affect of $\lambda , \mu $ on induced subgraph. certainly this kind of graph exist, I just don't know methods to give a formula saying that this parametrization will must have this kind of graph . $\endgroup$ – Jim Aug 5 '15 at 16:46
  • $\begingroup$ So I can see that having this property will be an invariant for a strongly regular graph, but you have to verify the property over all possible chains of adjacent vertices (you are not guaranteed that because this works for one sequence of vertices, it will work for all or that you will get the same subgraphs every time). How does that effect the algorithm? $\endgroup$ – Morgan Rodgers Aug 5 '15 at 17:12
  • $\begingroup$ 1 sequence of vertices (which consists total $y$ vertices ,each vertex of them fulfilling above condition for total all $y$ iteration) is enough! actually better!! because vertices become distinct . Is there any existing method that characterize graph for all iteration ? $\endgroup$ – Jim Aug 5 '15 at 17:50
  • $\begingroup$ check this : $D_1$ is also strongly regular graph.Consider $D_1$ as induced subgraph . if you add constant number of vertices to each vertex of $D_1$ graph it will be the graph $G$ and each vertex of $G$ has $\lambda , \mu$ parameters. So, $D_1$ has $\lambda- E_c , \mu-E_c$, thus , a strongly regular graph. is it correct ? $\endgroup$ – Jim Aug 6 '15 at 9:25
  • $\begingroup$ I am not understanding. Is your claim that $D_{1}$ is always strongly regular? I don't think this is true, for example in the Shrikhande graph the neighborhood of a point is a $6$-cycle. Also, even when it is true, you may get different (nonisomorphic) graphs depending on the choice of $x_{1}$. And given $D_{1}$, reconstructing $G$ may be extremely difficult, even knowing the parameters, and it may not even be possible to uniquely recreate $G$ in many cases. $\endgroup$ – Morgan Rodgers Aug 6 '15 at 11:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.