Gráfico regular con algunas restricciones de simetría

Question

Busco un grafo regular no completo para el que se cumplan las dos condiciones siguientes:

• para cada dos vértices adyacentes $u,v$ , $\left|N(u)\cap N(v)\right|=2$
• para cada dos vértices no adyacentes $u,v$ , $\left|N(u)\cap N(v)\right|=1$

donde $N(x)$ es el conjunto de vecinos de $x$ (excepto $x$ mismo).

Me parece bien sustituir 2 por 3, digamos (o en realidad, por cualquier constante positiva...). Jugué un poco con el lápiz y con el ordenador, y no pude encontrar tal.

Answer 1

Mirando a esta página He encontrado tres ejemplos con menos de 500 vértices: srg(209,16,3,1), srg(375,16,3,1) y srg(400,21,2,1). No tengo ni idea de cómo se construyeron estos grafos. póngase en contacto con el autor de esa página.

Edición: En realidad, si estoy entendiendo la notación de colores de las filas del primer sitio (verde=probablemente existe, amarillo=potencialmente existe, rojo=probablemente no existe), el único de esos que podría existir es el que tiene 400 vértices. He encontrado tres ejemplos más de parámetros factibles con $\mu=1$ pero todos eran de color rojo.