\documentstyle[a4,12pt]{article}
\title{Finite graphs in which the point neighbourhoods are the maximal
independent sets}
\author{A.E. Brouwer}
\begin{document}
\maketitle

\newcommand{\Zz}{{\bf Z}}
\newcommand{\isom}{\,\simeq\,}
\newcommand{\adj}{\,\sim\,}
\newcommand{\nadj}{\,\not\sim\,}
\newtheorem{Theorem} {Theorem} [section]
\newtheorem{Proposition} [Theorem] {Proposition}
\newtheorem{Lemma} [Theorem] {Lemma}
\newcommand{\Proof}{ \noindent{\bf Proof:}\quad }
\newcommand{\qed  }{\hfill$\Box$\medskip}

\begin{abstract}
We determine all graphs as in the title.
\end{abstract}

In \cite{vdH} certain graphs $L_k$ occur. Noticing that they
have the property mentioned in the title, I wondered
whether they are the only such graphs. This note shows
that, essentially, this is indeed the case.

For $k \le 1$, let $L_k$ be the graph with vertex set
$\Zz_{3k-1}$ (the integers mod $3k-1$) and adjacencies
$x \adj y$ iff $y - x \in \{ 1,4,7, ..., 3k-2 \}$.
(Thus, $L_1$ is the complete graph
on two vertices, and $L_2$ is the pentagon.)
The {\em neighbourhood} of a vertex $x$ is the set
$N(x) = \{ y | y \adj x \}$.
A graph $G$ is called {\em reduced} when distinct vertices
have distinct neighbourhoods.

\begin{Theorem}
The finite reduced triangle-free graphs in which each
independent set is contained in a point neighbourhood
are precisely the graphs $L_k$ $(k \ge 1)$.
\end{Theorem}
\Proof
First we show that the graphs $L_k$ have the stated property.
That they are finite, reduced and triangle-free is clear.
Now it suffices to show that if $S$ is an independent set
contained in $N(x)$, and $S \cup \{y\}$ is independent
for some $y$, $y \nadj x$, then $S \cup \{y\} \subseteq N(z)$
for some $z$. But $y = x+3i-1$ or $y = x+3i$ for some $i$
$(1 \le i \le k-1)$, and we can take $z = x+3i$ or $z = x+3i-1$,
respectively.

Conversely, let the graph $G$ have the stated property.
We show that $G \isom L_k$ for some $k \le 1$.
Since $\emptyset$ is independent, $G$ has a vertex,
and since a singleton is independent, each vertex has
a neighbour, and since two nonadjacent vertices have
a common neighbour, $G$ has diameter at most 2.
Clearly, if $G$ is complete, then $G \isom L_1$, so
we may assume that $G$ has diameter 2.

\medskip
Step 1. {\it Given two nonadjacent vertices $x$, $y$, there is
a unique vertex $z = \sigma (x;y)$ such that $y \adj z$ and
$N(x) \cap N(z) = N(x) \setminus (N(x) \cap N(y))$. \/}

\Proof
The set $\{y\} \cup N(x) \setminus (N(x) \cap N(y))$ is independent
and hence contained in $N(z)$ for some $z$. If it is also
contained in $N(z')$, then, since $G$ is reduced,
the vertices $z$ and $z'$ have distinct neighbourhoods, and we may
assume that $z \adj u$, $z' \nadj u$ for some vertex $u$.
But now $\{x,u,z'\}$ is independent and not contained in
a point neighbourhood. Contradiction.

\medskip
Step 2. {\it $G$ is regular of valency $k$, say. If $k > 1$,
then there is a pair of nonadjacent vertices with $k-1$
common neighbours.\/}

\Proof
Let $x,y$ be nonadjacent. If $| N(y) \setminus N(x) | > 1$,
then choose $u \in N(y) \setminus N(x)$, $u \neq \sigma (x;y)$.
By the uniqueness part of the previous step, there is a vertex
$v \in N(x) \setminus ( N(y) \cup N(u) )$, so that also
$| N(x) \setminus N(y) | > 1$.
Now $(N(x) \cap N(y)) \cup \{u,v\}$ is independent, and hence
contained in $N(z)$ for some $z$.
By downward induction on $|N(x) \cap N(y)|$ it follows that
$|N(x)| = |N(y)|$ (since we have either 
$|N(x)| = |N(x) \cap N(y)| + 1 = |N(y)|$, or,
by induction, $|N(x)| = |N(z)| = |N(y)|$).
Now regularity of $G$ follows since its complementary graph
$\overline{G}$ is connected.

\medskip
Step 3. {\it $G \isom L_k$. \/}

\Proof
Let $x_0 \nadj y_0$ and $|N(x_0) \cap N(y_0)| = k-1$.
Define vertices $x_i$, $y_i$ ($i \in \Zz$) by
$y_{i+1} = \sigma(x_i;y_i)$ and $x_i = \sigma(y_i;x_{i-1})$.
Then $|N(x_i) \cap N(y_i)| = k-1$ and
$N(x_i) \cap N(y_{i+1}) = \{x_{i-1}\} = \{y_{i+2}\}$ for all $i$.
By induction on $j$ $(1 \le j \le k-1)$ we see that
$|N(x_0) \cap N(x_{3j})| = k-j$, and that
$x_0 \adj x_1, x_4, ..., x_{3j-2}$ and
$x_{3j} \adj x_2, x_5, ..., x_{3j-1}$.
Indeed, for $j=1$ this is clear, since $x_0 = y_3$.
But $x_{3j}$ and $x_{3j+3}$ have the same neighbours
except for $x_{3j+1}$, $x_{3j+2}$, and $x_0$ and $x_{3j}$
have the same neighbours except for the vertices
$x_{3i+1}$, $x_{3i+2}$ ($0 \le i \le j-1$), so
$x_0 \adj x_{3j+1}$ and similarly $x_2 \adj x_{3j+3}$.
As long as $x_0$ and $x_{3j}$ have common neighbours,
it follows that $x_0 \neq x_{3j\pm 1}$.
However, $x_0$ and $x_{3k-1}$ have the same neighbours, so
$x_0 = x_{3k-1}$.
If there is a vertex $z$ distinct from all $x_i$, then $z$
is adjacent to either all or none of the $x_i$, contradiction,
since $G$ is triangle-free and connected.
\qed

This theorem can be generalized by deleting the hypothesis
that $G$ is reduced. Now the conclusion becomes that $G$ is
a coclique extension of one of the $L_k$.
(In particular, if $G$ is regular, that $G$ is a
lexicographic product $L_{k,m} := L_k [ \overline{K_m} ]$.)
Probably the finiteness hypothesis can be dropped as well,
but the conclusion becomes more complicated, and I have not
investigated this further.

The reason that the graphs $L_{k,m}$ occur in \cite{vdH}
is that (for $m \ge 3$) they have the maximal possible
toughness $t = n/k - 1$ for triangle-free regular graphs.
(The {\em toughness} $t(G)$ of a connected non-complete graph $G$
with vertex set $V$ is by definition
$\min |V \setminus X| / \omega (X)$
taken over all subsets $X$ of $V$ such that the number of
connected components $\omega (X)$ of $X$ is at least two.
Clearly, $t(G) \le (|V|-2)/2$.)

\begin{Lemma}
Let $G$ be a connected non-complete graph.
The toughness of the lexicographic product
$G[\overline {K_m}]$ equals
$\min |V \setminus X| / w(X)$, where $w(X)$ is the number
of singleton components of $X$ plus $1/m$-th of the number
of other components of $X$, and $X$ runs through the subsets of $V$
with $\omega (X) > 1$.
\qed
\end{Lemma}

\begin{Proposition}
The toughness of $L_{k,m}$ equals $\min ( 2 - {1 \over k},
2 - {2 \over {m(k-1)+1}} )$ $(k \ge 1,~ m \ge 1)$.
\end{Proposition}
\Proof
By the above lemma, we only have to investigate $G = L_k$.
Taking $X = N(0)$ shows that $t(G) \le (3k-1-k)/k = 2 - 1/k$.
Taking $X = N(0) \cup \{2\}$ shows that
$t(G) \le ((3k-1)-(k-1))/(k-1+1/m) = 2 - 2/(m(k-1)+1)$.
Conversely, if $\{x,y\}$ is an edge of $G$, then
$V \setminus (N(x) \cup N(y))$ is complete bipartite
or a coclique. Thus, if some subgraph $X$ of $G$ has
at least two non-singleton components, then $w(X) = 2/m$
and $|V \setminus X| / w(X) \ge 4/(2/m) = 2m \ge 2$
so that $X$ does not determine the toughness.
If $X$ has precisely one non-singleton component,
say containing the edge $\{0,3t+1\}$, then the set
$S$ of all vertices $s$ such that $\{s\}$ is a component of $X$
is contained in one part of the bipartition on the vertices nonadjacent
to both $0$ and $3t+1$; say, $S \subseteq \{3t+3,...,3k-3\}$.
Now $|V \setminus X| / w(X) \ge |N(S)| / (|S| + 1/m)$. But when
$|S|$ is given, $|N(S)|$ is minimal when $S$ is `consecutive':
$S = \{3a,3a+3,...,3a+3r\}$, and then $|N(S)| / (|S| + 1/m) =
(k+r)/(r+1+1/m)$. This again is minimal when $|S|$ is maximal,
i.e., for $t = 0$ and $r = k-2$, and then
$|N(S)| / (|S| + 1/m) = 2 - 2/(m(k-1)+1)$.
Finally, if $X$ has only singleton components, a similar
but easier argument again shows that we get the smallest
quotient by taking $X$ a maximal coclique, and then this quotient
equals $2 - 1/k$.
\qed 

\begin{thebibliography}{}

\bibitem[vdH]{vdH} Jan van den Heuvel,
{\it Degree and Toughness Conditions for Cycles in Graphs\/},
Ph.D. thesis, Techn. Univ. Twente, 1993.

\end{thebibliography}

\end{document}
