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, 2015 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, 2015 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$ Jan 28, 2015 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, 2015 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$ Jan 28, 2015 at 12:05

1 Answer 1


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, 2015 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$ Jan 28, 2015 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, 2015 at 18:28
  • $\begingroup$ Is the number 266 simply the total number of 8-vertex graphs of maximal degree 2? $\endgroup$ Jan 28, 2015 at 18:45
  • $\begingroup$ That number was in fact incorrect. The correct number is 6. $\endgroup$
    – Jernej
    Jan 28, 2015 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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