Consider a strongly regular graph $G$ with parameters $(76,30,8,14).$ Hoffman's bound tells us that $\overline{G}$ has an independent set of size at most $4$ and its not hard to see there are indeed $4$ independent vertices in $\overline{G}.$

So if $x \in V(G)$ then the graph $H$ induced by $N(v)$ is a $8$-regular, $K_4$-free graph on $30$ vertices and known bounds tell us that $\alpha(H) \ge 5.$

Hence $G$ must must contain $K_{1,5}$ as an induced subgraph. I do not see any way to extend this subgraph without introducing cases.

What I am wondering is

Question 1. Can someone construct larger graphs that must be present as induced subgraphs of $G$


Question 2. Can someone find large induced subgraphs for some of the missing SRG's on less than 100 vertices?

The motivating factor for this problem is that getting an induced subgraph of order 19 not having $2$ as an eigenvalue is enough to reconstruct $G.$

  • $\begingroup$ What will you reconstruct if the SRG is not unique? $\endgroup$ – joro Jan 22 '15 at 14:34
  • $\begingroup$ @joro If one can find an unique such graph then the method in question will give you all possibilites. Though my hope is to start with a large induced subgraph and extend it to many candidates of order 19. $\endgroup$ – Jernej Jan 22 '15 at 14:52
  • $\begingroup$ in my old papers I reconstructed subgraphs induced on the common neighbours of a pair of non-adjacent vertices. But it was always the case that I knew much more about $N(v)$ than here. $\endgroup$ – Dima Pasechnik Jan 28 '15 at 9:40
  • $\begingroup$ @DimaPasechnik Speaking of this concrete case... Using interlacing for pruning one can construct the graphs induced by $N(v) \cap N(u)$ for adjacent as well as non-adjacent vertices. I have both lists. I'll check if your paper offers any insights how to go from there :-) $\endgroup$ – Jernej Jan 28 '15 at 12:00
  • $\begingroup$ @Jernej : basically, it might be possible to reconstruct all the possibilities for $N(v)$ using your lists (provided they aren't very long...). And this would be almost it (again, depending upon how long the resulting list is). $\endgroup$ – Dima Pasechnik Jan 28 '15 at 12:05

On strategies of reconstructing bigger subgraphs: suppose for a vertex $v$ we have we know the set $M$ of (possible) subgraphs $G(v,w)$ induced on $N(v,w):=N(v)\cap N(w)$, for a vertex $w$ at distance 2 from $v$, and the set $\Lambda$ of (possible) subgraphs $G(v,u)$ induced on $N(v,u)$, for $u\in N(v)$.

Take $H\in M$ and $F\in\Lambda$ so that they match on $N(u,v)$ and on $N(u,w)$, for $w\in N(u)-N(v)$ (i.e. we identify $H$ with $G(v,w)$ and $F$ with $G(v,u)$). Now, let us pick $w\neq w_1\in N(u)-N(v)$, and go though all the possible $H_1\in M$ so that in addition $H_1$ can be identified with $G(v,w_1)$; for each success we can further pick $w_2\in N(u)-N(v)-\{w,w'\}$ and go through all the possible $H_2\in M$ so that $H_2$ can be identified with $G(v,w_2)$, etc. One possible variation here is to switch the roles of $u$ and $v$ and reconstruct subgraphs in $N(u)$ in the same vein.

If such a search tree does not get too big, one can think of what to do next.

  • $\begingroup$ Let me restate the precise fact here. If $u \sim v$ and $w \in N(u) \cap N(v)$ then $|N(u) \cap N(v) \cap N(w) | \leq 2$ In particular the induced subgraph is either empty, $K_1$ or $2K_1.$ $\endgroup$ – Jernej Jan 28 '15 at 18:23
  • $\begingroup$ So, how about $u\neq w\not\in N(u)$, but $w\in N(v)$? This is what you can extract from that 375219 examples... $\endgroup$ – Dima Pasechnik Jan 28 '15 at 18:26
  • $\begingroup$ I'll be able to give this result soon (an hour or so) - I am recomputing the list of graphs induced by $N(u) \cap N(v)$ when $u \not \sim v.$ Fingers crossed we get the same bound. $\endgroup$ – Jernej Jan 28 '15 at 18:28
  • $\begingroup$ Is the number 266 simply the total number of 8-vertex graphs of maximal degree 2? $\endgroup$ – Dima Pasechnik Jan 28 '15 at 18:45
  • $\begingroup$ That number was in fact incorrect. The correct number is 6. $\endgroup$ – Jernej Jan 28 '15 at 18:47

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.