Expressing locally linear in terms of integer programming

Question

A locally linear graph $G=(V,E)$ is a graph whose adjacent vertices have exactly one common neighbor, i. e.

$$\forall(\{i,j\}\in E)\exists!(k\in V):\{i,k\}\in E\wedge\{j,k\}\in E$$

I'm trying to generate random locally linear graphs using integer programming. The variable $x_{i,j}$ corresponds to the edge $\{i,j\}$. Also, the variable $z_{i,j,k}$ is nonzero iff both $x_{i,k}$ and $x_{j,k}$ are nonzero (i. e. when $k$ is a common neighbor of $i$ and $j$). The value of $z_{i,j,k}$ is determined by constraints decribed here. Now I'm trying to choose constraints $C$ such that given any objective function, a solution satisfying $C$ corresponds to a locally linear graph. So far, I use the strong constraints of the form $x_{i,j}+\sum\limits_{k}z_{i,j,k}=2$ (*). This indeed gives a locally linear graph since when $x_{i,j}=1$, we have $\sum\limits_{k}z_{i,j,k}=1$ (thus adjacent vertices $i$ and $j$ have exactly one common neighbor). But * also give the redundant property of a graph: any two nonadjacent vertices have exactly two common neighbors. Can I use here some other constraints or variables to generate any locally linear graph (not necessarily possessing the last property)?

Answer 1

1. $\forall i,j;\;\; x_{i,j} \le \sum_k z_{i,j,k}$
2. $\forall i,j;\;\; \sum_k z_{i,j,k} \le M(1-x_{i,j}) +1$

If $x_{i,j} = 0$ then $\sum_k z_{i,j,k}$ can be whatever. If $x_{i,j} = 1$ then constraints 1. gives $1\le \sum_k z_{i,j,k}$ and constraints 2 gives $\sum_k z_{i,j,k} \le 1$.

Answer 2

$2z_{i,j}^k \le x_{i,k}+x_{j,k} \le 3-z_{i,j}^k \ \ \forall k \in V - \{i,j \}$

$\sum_{k \in V - \{i,j \}}z_{i,j}^k = x_{i,j} \ \ \forall (i,j) \in E$