\documentclass{amcjou}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{newlfont}
\usepackage{graphicx}
\usepackage{multicol}
\usepackage{doc}
\usepackage{color}
\usepackage{algpseudocode}
\newtheorem{theorem}{Theorem}
\newtheorem{problem}{Problem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\begin{document}
% Your \newcommands below (if there are any):
\newcommand{\mqed}{\quad\hfill\rule{1.5ex}{1.5ex}\vspace{1mm}\smallskip}
\begin{frontmatter} %% Title, information about author, abstract, etc.
\titledata{On $\pm 1$ eigenvectors of graphs}
{}
\authordata{Dragan Stevanovi\'c}
{Mathematical Institute of the Serbian Academy of Science and Arts, Knez Mihajlova 36, 11000 Belgrade, Serbia
and University of Primorska, Institute Andrej Maru\v si\v c, Muzejski trg 2, 6000 Koper, Slovenia}
{dragan.stevanovic@upr.si}
{The author was supported by
the research program P1-0285 and the research projects J1-5433, J1-6720, J1-6743, and J7-6828 of the Slovenian Research Agency and
the research grant ON174033 of the Ministry of Education and Science of Serbia.}
\begin{center}
{\bf Dedicated to the memory of Ante Graovac}
\end{center}
\begin{abstract}
While discussing his spectral bound on the independence number of a graph,
Herbert Wilf asked back in 1986
what kind of a graph admits an eigenvector consisting solely of $\pm 1$~entries?
We prove that Wilf's problem is NP-complete,
but also that the set of graphs having a $\pm 1$ eigenvector is quite rich,
being closed under a number of different graph compositions.
\keywords{Eigenvector; Adjacency matrix; Wilf's problem.}
\msc{05C50}
\end{abstract}
\end{frontmatter} %% End of the front matter
%% Your article
\section{Introduction}
Chemical graphs, defined as simple, connected, unweighted graphs with the maximum vertex degree at most three,
correspond to carbon skeletons of known and potential $\pi$-conjugated hydrocarbon molecules, and
their adjacency spectra provide models for energies of the $\pi$-molecular orbitals of such systems
within the simple H\"uckel approach~(see, e.g., \cite{GuPo}).
Restriction on the maximum vertex degree confines the eigenvalues of a chemical graph to the interval $[-3,+3]$.
Jerry Ray Dias~\cite{Dias} noted that the examples of chemical graphs with adjacency eigenvalues
$1$, $\sqrt2$, $\sqrt3$, $2$, $\sqrt5$, $\sqrt6$, $\sqrt7$ and $3$
are all readily found, and he discussed structural factors associated with the presence of each of these eigenvalues.
However, he could not find any chemical graph with eigenvalue~$\sqrt8$ and
made an intriguing conjecture \cite[$\S6$]{Dias} that no such graph exists.
Together with Patrick Fowler and Marko Milo\v sevi\'c,
the present author disproved Dias' conjecture by giving a number of constructions of chemical graphs with the eigenvalue~$\sqrt8$ in~\cite{FoSM}.
One particular construction, showcased in Fig.~\ref{fig-4k}, stands out
as it relies on a curious property of cycles with $4k$ vertices---%
that its vertices can be partitioned into two sets such that
the neighbors of each vertex are equinumerously divided among both sets.
This property is easily seen to be equivalent to the existence of a $\pm 1$ eigenvector corresponding to the adjacency eigenvalue~$0$.
\begin{figure}
\begin{center}
\includegraphics[angle=90, scale=0.5]{4k.pdf}
\end{center}
\caption{\em Construction of a graph with the maximum degree three and eigenvalue~$\sqrt8$
from $4k$ copies of smaller such graph containing a leaf.
Copies of the local eigenvector corresponding to the eigenvalue~$\sqrt8$ are taken with the signs $+,+,-,-,+,+,-,-,\dots$
to give an eigenvector corresponding to the eigenvalue $\sqrt8$ in the larger graph.
(Reprinted from \cite{FoSM}.)
}
\label{fig-4k}
\end{figure}
Quite some time later, while meticulously preparing his research monograph on the spectral radius of graphs~\cite{Stev},
the first author found out that Herbert Wilf had asked already in 1986
what kind of a graph admits an eigenvector consisting solely of $\pm 1$ entries?
In Wilf's case,
the question arised in the discussion of his spectral bound on the independence number of regular graphs~\cite{Wilf}.
Although the question explicitly asks just for a $\pm 1$ eigenvector of a graph,
it is implicitly assumed in~\cite{Wilf} that
such an eigenvector corresponds to the smallest eigenvalue of a regular graph.
This implicit assumption renders the question nearly impossible to answer in a simple manner,
as there exist strongly regular graphs with the same parameter set
such that some of them have and the others do not have a $\pm 1$ eigenvector corresponding to the smallest eigenvalue.
We will, therefore, treat Wilf's question in its more general form and
consider the problem of the existence of a $\pm 1$ eigenvector corresponding to any eigenvalue of a graph.
The paper is organized as follows.
In the rest of this section we list necessary definitions and preliminaries.
In Section~\ref{sc-NPcomplete} we prove that this problem is polynomially reducible to
the problem of the existence of a $\pm 1$ eigenvector corresponding to the eigenvalue~$0$,
and that the latter problem is NP-complete.
In Section~\ref{sc-algorithm} we give a simple and straightforward algorithm for solving both problems,
and use it to show that the three Chang graphs all have a $\pm 1$ eigenvector corresponding to the smallest eigenvalue,
while $L(K_8)$, the fourth $(28,12,6,4)$-strongly regular graph, does not have such an eigenvector.
Nevertheless, we show in Section~\ref{sc-constructions} that
the set of graphs with a $\pm 1$ eigenvector corresponding to the eigenvalue~$0$ has rich structure,
being closed under a number of different graph compositions.
Cartesian product of two graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ is
the graph $G_1+G_2$ with the vertex set $V_1\times V_2$ such that
two vertices $(u_1,u_2)$ and $(v_1,v_2)$ are adjacent in $G_1+G_2$
if either $u_1=v_1$, $(u_2,v_2)\in E_2$ or $(u_1,v_1)\in E_1$, $u_2=v_2$.
Cartesian product of graphs is a special case of a more general graph composition, called the NEPS of graphs.
Let $\mathcal{B}$ be a set of nonzero binary $n$-tuples, i.e., $\mathcal{B}\subseteq\{0,1\}^n\setminus\{(0,\dots,0\}$,
such that for every $i=1,\dots,n$ there exists $\beta\in\mathcal{B}$ with $\beta_i=1$.
The {\em non-complete extended $p$-sum} of graphs $G_1=(V_1,E_1),\dots,G_n=(V_n,E_n)$ with the basis $\mathcal{B}$,
denoted by $\mathrm{NEPS}(G_1,\dots,G_n;\mathcal{B})$, is the graph with the vertex set $V_1\times\cdots\times V_n$
in which two vertices $u=(u_1,\dots,u_n)$ and $v=(v_1,\dots,v_n)$ are adjacent if and only if
there exists $\beta\in\mathcal{B}$ such that for $i=1,\dots,n$ holds
$u_i=v_i$ if $\beta_i=0$ and $(u_i,v_i)\in E_i$ if $\beta_i=1$.
The {\em Kronecker product} $A\otimes B$ of matrices $A=(a_{ij})_{m,n}$ and $B=(b_{ij})_{p,q}$ is
the $mp\times nq$ matrix obtained from $A$ by replacing each entry $a_{ij}$ by the block $a_{ij}B$.
It is well known (see, e.g., \cite{MaMi}) that
the Kronecker product is distributive with respect to the standard product of matrices:
\begin{equation}
\label{eq-kronecker}
(AB)\otimes(CD)=(A\otimes C)(B\otimes D).
\end{equation}
%The partition $V=V_1\cup\dots\cup V_k$ of the vertex set~$V$ of a graph~$G$ is
%the {\em equitable partition} of~$G$
%if each vertex in $V_i$ has the same number $b_{i,j}$ of neighbors in~$V_j$ for each $i$ and $j$.
%The matrix $B=(b_{ij})$ is the {\em quotient matrix} of the equitable partition and
%it is well known that the eigenvalues of~$B$ are also the eigenvalues of the adjacency matrix of~$G$
%(see, e.g., \cite[Section 2.3]{BrHa}).
\section{NP-completeness of the existence of $\pm 1$-eigenvectors}
\label{sc-NPcomplete}
We start by showing that in order to be able to decide
if the adjacency matrix of a graph has a $\pm 1$ eigenvector associated to an arbitrary eigenvalue,
it is sufficient to know how to decide if the adjacency matrix has a $\pm 1$-eigenvector corresponding to the eigenvalue~0.
%Recall that two problems are polynomially equivalent if each is polynomially reducible to the other.
\medskip\noindent
{\bf PMEIG problem.}\
Given a simple graph $G$ with an adjacency matrix~$A$,
find an eigenvector of~$A$ all of whose entries are equal to either $+1$ or~$-1$,
if it exists.
\medskip\noindent
{\bf PMEIG0 problem.}\
Given a simple graph $G$ with an adjacency matrix~$A$,
find an eigenvector of~$A$ corresponding to the eigenvalue~0,
all of whose entries are equal to either $+1$ or $-1$,
if it exists.
\smallskip
\begin{theorem}
{\bf PMEIG} is polynomially reducible to {\bf PMEIG0}.
\end{theorem}
\begin{proof}
Let $G$ be an $n$-vertex simple graph with an adjacency matrix~$A$.
If $G$ has a $\pm 1$ eigenvector~$x$ corresponding to some eigenvalue~$\lambda$ of~$A$, then from
$$
Ax=\lambda x
$$
and the fact that the entries of $Ax$ and $x$ are integers,
we conclude that $\lambda$ must be an integer itself.
($\lambda$ cannot be a rational number
as it is a root of the monic polynomial $\det(\lambda I-A)$ with integer coefficients.)
The value $|\lambda|$ is bounded from above by the spectral radius $\lambda_1(A)$ by the Perron-Frobenius theorem,
which is further bounded from above by the maximum vertex degree $\Delta$ by the Rayleigh quotient
(see, e.g., \cite[pp. 8--11]{Stev} for the discussion of the Perron-Frobenius theorem and the Rayleigh quotient).
Thus,
\begin{equation}
\label{eq-lambda-feasible}
\lambda\in\{-\Delta,\dots,\Delta\}.
\end{equation}
Recall that
the adjacency spectrum of the Cartesian product $G+H$ of two graphs $G$ and~$H$ is fully described
by the adjacency spectra of $G$ and~$H$ (see, e.g., \cite[pp. 30--32]{CvRS}):
if $\lambda$ is an eigenvalue of~$G$ with an eigenvector~$x$
and $\mu$ is an eigenvalue of~$H$ with an eigenvector~$y$,
then $\lambda+\mu$ is the eigenvalue of~$G+H$ with the eigenvector $x\otimes y$,
where $\otimes$ denotes the Kronecker product of matrices.
Moreover, all eigenvalues and eigenvectors of $G+H$ are representable in this form.
It is well-known that the adjacency spectrum of the complete bipartite graph~$K_{m,m}$ consists of
the simple eigenvalue~$m$ with the all-one eigenvector~$j^+$,
the simple eigenvalue~$-m$ with the eigenvector $j^-$
whose entries are equal to~1 in one part and to~$-1$ in the other part of the bipartition,
and the eigenvalue~0 of multiplicity $2m-2$.
Thus, if $G$ has an integer eigenvalue $\lambda$ with a $\pm 1$ eigenvector~$x$,
then $G+K_{|\lambda|,|\lambda|}$ has an eigenvalue~$0$
with the corresponding $\pm 1$ eigenvector equal to either $x\otimes j^+$ or $x\otimes j^-$.
We see that, due to~(\ref{eq-lambda-feasible}),
to solve {\bf PMEIG} it is enough to solve {\bf PMEIG0} for the $\Delta+1\leq n$ graphs
$$
G,\quad G+K_{1,1},\quad G+K_{2,2},\quad \dots,\quad G+K_{\Delta,\Delta}.
$$
Since these graphs have $n$, $2n$, $4n$, \dots, $2\Delta n$ vertices, respectively,
this represents a polynomial-time Turing reduction from {\bf PMEIG} to {\bf PMEIG0}.
\end{proof}
Next,
observe that each $\pm 1$ eigenvector $x$ of $A$ corresponding to the eigenvalue~$0$
determines the partition $V=V^+_x\cup V^-_x$ of the vertex set~$V$ of~$G$:
\begin{eqnarray*}
V^+_x &=& \{ u\in V \,\colon\, x_u=1 \}, \\
V^-_x &=& \{ u\in V \,\colon\, x_u=-1 \}.
\end{eqnarray*}
Due to
$$
Ax=0
$$
and the fact that for each $u\in V$
\begin{equation}
\label{eq-neighborsum}
(Ax)_u = \sum_{v\sim u} x_v,
\end{equation}
we see that the partition $V^+=V^+_x$, $V^-=V^-_x$ satisfies:
\begin{equation}
\label{eq-eigencondition}
\begin{array}{c}
\mbox{\em For each vertex $u\in V$ the number of its neighbors in~$V^+$} \\
\mbox{\em is equal to the number of its neighbors in~$V^-$.}
\end{array}
\end{equation}
We will say that a graph $G$ with the vertex set~$V$ is {\em eigenpartite}
if there exists a partition $V=V^+\cup V^-$, $V^+\cap V^-=\emptyset$, satisfying the property~(\ref{eq-eigencondition}).
From (\ref{eq-neighborsum}) it is obvious that
if $G$ is eigenpartite,
then $G$ has a $\pm 1$ eigenvector~$x$ corresponding to the eigenvalue~$0$,
obtained by setting its components to~$+1$ for vertices in~$V^+$ and to~$-1$ for vertices in~$V^-$.
Hence {\bf PMEIG0} is equivalent to the problem of eigenpartiteness of~$G$.
The proof of the following theorem was communicated to the author by Brendan McKay and L\'aszl\'o Lov\'asz.
\begin{theorem}
\label{th-laci}
{\bf PMEIG0} is NP-complete.
\end{theorem}
\begin{proof}
We prove this theorem by reducing a known NP-complete problem to {\bf PMEIG0}.
For an integer $k\geq 2$, a {\em $k$-uniform hypergraph} $H$ is an ordered pair $H=(V,E)$,
where the set of vertices~$V$ is a finite nonempty set, and
the set of edges~$E$ is a family of distinct $k$-subsets of~$V$.
A hypegraph $H=(V,E)$ is {\em 2-colorable}
if it admits a partition of its vertex set~$V$ into two color classes so that no edge in~$E$ is monochromatic.
It was shown in~\cite{Lova} that
deciding 2-colorability of $k$-uniform hypergraphs is NP-complete for every fixed $k\geq 3$.
Even more, deciding 2-colorability of a 4-uniform hypergraph
so that each edge has two vertices of each color is also NP-complete.
Take an instance $H=(V,E)$ of the latter hypergraph problem.
Construct a simple graph~$G$ with the vertex set $V\cup E'\cup E''$,
where $E'$ and $E''$ are two copies of~$E$:
$$
E' = \{ e' \,\colon\, e\in E \},
\qquad
E'' = \{ e'' \,\colon\, e\in E\}.
$$
For each edge $e' = e'' = \{w,x,y,z\}$ of $H$, $G$ contains the edges
$$
\{e'w,e'x,e'y,e'z,e''w,e''x,e''y,e''z\}.
$$
If the hypergraph $H$ has a 2-coloring so that each edge has two vertices of each color,
then the graph $G$ is eigenpartite:
partition $V$ as $V'\cup V''$ according to the 2-coloring of~$H$,
put all of~$E'$ in one part and all of~$E''$ in the other part.
The neighbors of each vertex~$u$ in~$V$ of~$G$ are
those elements of $E'$ and~$E''$ that correspond to the edges of~$E$ in~$H$ incident to~$u$,
so that $u$ satisfies (\ref{eq-eigencondition}).
The neighbors of each vertex~$e'$ in~$E'$ of~$G$ are
those vertices of $V$ that are incident to the corresponding edge~$e$ in~$H$,
of which two are in $V'$ and the other two are in~$V''$,
so that $e'$ satisfies (\ref{eq-eigencondition}) as well.
Conversely, if the graph $G$ is eigenpartite,
then the hypergraph $H$ is 2-colorable with each edge having two vertices of each color:
just color the vertices of $V$ according to the eigenpartition.
\end{proof}
\section{An exhaustive search algorithm for PMEIG0}
\label{sc-algorithm}
The eigenspace $\mathcal{E}_0$ of the eigenvalue~$0$ of~$A$, as a kernel of~$A$, consists of
vectors whose entries are coefficients of linear combinations of the columns of~$A$ with value equal to~$0$.
To compute the basis of~$\mathcal{E}_0$
it thus suffices to compute the column echelon form $\begin{bmatrix} B \\ C \end{bmatrix}$
of the row augmented matrix~$\begin{bmatrix} A \\ I \end{bmatrix}$.
During the computation of the column echelon form of~$A$,
the identity matrix in $\begin{bmatrix} A \\ I \end{bmatrix}$ serves
to keep track of the coefficients of linear combinations of columns of~$A$
which yield the columns of~$B$.
Thus, the basis of $\mathcal{E}_0$ consists of those (nonzero) columns of~$C$
for which the corresponding column of~$B$ is a zero column.
Since the entries of $A$ and~$I$ are integers,
the column echelon form can be computed in integer arithmetic by Bareiss algorithm~\cite{Bare}.
\bigskip
{\small
\begin{algorithmic}
\hrule
\State INPUT: An $n\times n$ adjacency matrix~$A$
\State OUTPUT: A $\pm 1$-eigenvector~$x$ of the eigenvalue~$0$ of~$A$, if it exists
\State
\State Use Bareiss algorithm to compute
the column echelon form $\begin{bmatrix} B \\ C \end{bmatrix}$
of $\begin{bmatrix} A \\ I \end{bmatrix}$
\State
\State $D\gets$ the nonzero columns of~$C$ such that the corresponding column of~$B$ is~0
\If {$D$ is empty}
\State {\bf return} ``there is no such eigenvector''
\EndIf
\State
\State $k\gets$ the number of columns of~$D$
\State $U\gets$ the set of row indices of~$D$ yielding a submatrix $E$ of rank~$k$
\State
\For{each $z\in\{-1,+1\}^{U}$}
\State solve the linear system $E y = z$
\State $x\gets Dy$
\If{$x$ is a $\pm 1$ vector}
\State {\bf return} $x$
\EndIf
\EndFor
\State
\State {\bf return} ``there is no such eigenvector''
\smallskip
\hrule
\end{algorithmic}
}
\bigskip
The second part of the algorithm then exhaustively searches the set of all $\pm 1$ vectors over~$U$
for their potential extensions to the full $\pm 1$ eigenvector of the eigenvalue~$0$:
any $z\in\{-1,+1\}^{U}$ can be uniquely written as $z=Ey$, since $E$ has the full rank,
and then $x=Dy$ is the unique eigenvector of~$0$ that coincides with~$z$ over~$U$.
Since Bareiss algorithm has polynomial running time,
the time complexity of the above algorithm is controlled by multiplicity of the eigenvalue~$0$.
Although it is believed that almost all graphs have simple eigenvalues only
(which is supported by a recent proof of Tao and Vu \cite{TaVu} of Babai's conjecture
that the Erd\"os-R\'enyi random graph $G(n,\frac12)$ has all simple eigenvalues with probability $1-o(1)$),
the problem with the above algorithm, as expected, is
that most of the interesting graphs, to which we would like to apply it, do have high multiplicity of the eigenvalue~$0$.
For example, the graph constructed in Theorem~\ref{th-laci}
in the reduction from the problem of 2-coloring 4-uniform hypergraph $H=(V,E)$ to {\bf PMEIG0},
is bipartite with the bipartition $(V, E'\cup E'')$.
Multiplicity of its eigenvalue~$0$ is then, according to~\cite{CvGu},
at least the difference $2|E|-|V|$ in sizes of its bipartition,
so that the above algorithm then has running time complexity not less than $2^{2|E|-|V|}$.
The above algorithm can be used to test existence of a $\pm 1$ eigenvector
for any other fixed eigenvalue~$\lambda$ of the adjacency matrix~$A$
simply by supplying $A-\lambda I$ instead of~$A$ to it.
We have run this algorithm on the triangular graph $L(K_8)$ and the three Chang graphs cospectral to it.
Recall that the triangular graph is the line graph $L(K_m)$,
defined on the pairs of an $n$-set,
with two pairs adjacent if they have an element in common.
It is a strongly regular graph with the parameters $(\nu,k,\lambda,\mu)=(m(m-1)/2,2(m-2),m-2,4)$.
Chang~\cite{Chan,Chan2} and Hoffman~\cite{Hoff} proved that
if $G$ is a strongly regular graph with these parameters,
then for $m\neq 8$, $m\geq 4$, $G$ is isomorphic to the triangular graph~$L(K_m)$,
while for $m=8$, $G$ is isomorphic either to $L(K_8)$ or to one of three Chang graphs.
For $m=8$, all four of these graphs have the adjacency spectrum $[12, 4^{(7)}, -2^{(20)}]$, with exponents denoting multiplicities.
Interestingly, the above algorithm reports that
each of the three Chang graphs has a $\pm 1$ eigenvector corresponding to the least eigenvalue~$-2$,
while the triangular graph $L(K_8)$ does not have such eigenvector.
Since these four graphs share the same local neighborhood structure,
it becomes apparent that one could hardly hope to find a simple answer to
Wilf's implicit question of existence of a $\pm 1$ eigenvector corresponding to the smallest eigenvalue of a regular graph.
\section{Constructions of eigenpartite graphs}
\label{sc-constructions}
Although it is NP-complete to check whether a given graph is eigenpartite,
sheer simplicity of its defining condition~\ref{eq-eigencondition} makes it easy to construct new eigenpartite graphs.
Probably the simplest way to construct an eigenpartite graph from an arbitrary graph~$G$ is
by taking two copies of it and adding edges between different copies in accordance to~$G$:
an edge is added between two vertices in different copies whenever these vertices are adjacent in~$G$.
$V^+$ is then formed by the vertices in one copy, and $V^-$ by the vertices of the other copy of~$G$.
A few more constructions are variations on this theme:
\begin{itemize}
\item
(Suggested by Brendan McKay.)
Suppose that $G$ and $H$ are graphs with degree sequences $S$ and~$T$, respectively,
such that $(S,T)$ is also degree sequence of a bipartite graph~$K$ with the bipartition $(U,V)$.
An eigenpartite graph is obtained by superimposing~$G$ on the vertices of~$U$ in accordance to~$S$,
and by superimposing~$H$ on the vertices of~$V$ in accordance to~$T$.
$(U,V)$ then represents the eigenpartition of this new graph.
\item
(Suggested by Ross Kang.)
Let $G$ be an eigenpartite graph with an eigenpartition $(V^+,V^-)$.
Replace each vertex of~$G$ with an independent set of $k$~vertices.
Between two distinct independent $k$-sets corresponding to adjacent vertices in~$G$,
superimpose an arbitrary $j$-regular bipartite graph on $k + k$ vertices.
One part of the eigenpartition of the new graph is then formed by the $k$-sets corresponding to the vertices in~$V^+$,
and the other part by the $k$-sets corresponding to the vertices in~$V^-$.
\item
(Suggested by Ross Kang.)
Let $G$ be a $2s$-regular eigenpartite graph with an eigenpartition $(V^+,V^-)$.
Choose positive integers $m,n,p,q,r$ such that $s p + m = sq = s r + n$.
Replace each vertex of $V^+$ by an $m$-regular graph, and replace each vertex of $V^-$ by an $n$-regular graph.
Between the subgraphs corresponding to two neighbouring vertices of $V^+$ superimpose a bipartite $p$-regular graph;
between the subgraphs corresponding to two neighbouring vertices of $V^-$ superimpose a bipartite $r$-regular graph;
between the subgraphs corresponding to a vertex of $V^+$ adjacent to a vertex of $V^-$ superimpose a bipartite $q$-regular graph.
Similarly, one part of the eigenpartition of the new graph is then formed by the subgraphs corresponding to the vertices in~$V^+$,
and the other part by the subgraphs corresponding to the vertices in~$V^-$.
\end{itemize}
The set of eigenpartite graphs is, in addition, closed to taking arbitrary NEPS.
Important property of $\mathrm{NEPS}(G_1,\dots,G_n;\mathcal{B})$ is that
its spectrum can be represented by the spectra of $G_1,\dots,G_n$ \cite[Theorem 2.3.4]{CvRS}:
if $\lambda_i$ is an eigenvalue of~$G_i$ with the corresponding eigenvector~$x_i$, for $i=1,\dots,n$,
then
$$
\Lambda = \sum_{\beta\in\mathcal{B}} \lambda_1^{\beta_1}\cdots\lambda_n^{\beta_n}
$$
is the eigenvalue of~$\mathrm{NEPS}(G_1,\dots,G_n;\mathcal{B})$
with the corresponding eigenvector
$$
x = x_1\otimes\cdots\otimes x_n,
$$
where $\otimes$ denotes the Kronecker product of matrices.
Thus, if each $x_i$ is a $\pm 1$ eigenvector corresponding to the eigenvalue~$0$ of~$G_i$,
then $x=x_1\otimes\cdots\otimes x_n$ is a $\pm 1$ eigenvector corresponding to the eigenvalue~$0$ of $\mathrm{NEPS}(G_1,\dots,G_n;\mathcal{B})$.
Many standard graph products are instances of NEPS:
the Cartesian product of two graphs is obtained for the basis $\mathcal{B}=\{(1,0),(0,1)\}$,
the direct product for $\mathcal{B}=\{(1,1)\}$, and
the strong product for $\mathcal{B}=\{(1,1),(1,0),(0,1)\}$.
The last construction we present here
relies on partial Cartesian product of graphs~\cite{Yero}.
Let $G=(V,E)$ and $H=(W,F)$ be two graphs.
For $S\subseteq V$,
the {\em partial Cartesian product} of $G$ and $H$ with respect to~$S$ is
the graph $G+_SH$ with the vertex set $V\times W$,
with two vertices $(v_1,w_1)$ and $(v_2,w_2)$ adjacent if and only if
either $v_1=v_2\in S$ and $(w_1,w_2)\in F$
or $(v_1,v_2)\in E$ and $w_1=w_2$.
If $S=V$ then $G+_SH$ is just the standard Cartesian product $G+H$,
while if $S=\{v\}$ is a singleton, then $G+_{\{v\}}H$ is a particular case of the rooted product of graphs~\cite{GoMc}.
%\textcolor{red}{
%It might perhaps be possible to obtain a formula for the characteristic polynomial of the partial Cartesian product $G+_SH$
%in terms of the characteristic polynomials of $G$, $H$ and the subgraph of~$G$ induced by~$S$,
%but having in mind that the only way to get a characteristic polynomial of the Cartesian product of $G$ and $H$ is
%by resultants, I am not sure that it is worthwhile investing time in the search for a necessarily even more complicated expression \dots
%}
%\bigskip
If $A_G$ and $A_H$ are adjacency matrices of $G$ and~$H$, respectively,
then the adjacency matrix $A$ of $G+_SH$ is given by
$$
A = I_S\otimes A_H + A_G\otimes I,
$$
where $I_S$ is the diagonal matrix defined as
$$
(I_S)_{u,v} = \left\{
\begin{array}{rl}
1, & \mbox{if }u=v\in S, \\
0, & \mbox{otherwise},
\end{array}
\right.
$$
and $I$ is the standard unit matrix.
If $x$ is an eigenvector corresponding to the eigenvalue~$\lambda$ of~$G$
and $y$ is an eigenvector corresponding to the eigenvalue~$0$ of~$H$,
then from (\ref{eq-kronecker})
$$
A(x\otimes y) = (I_Sx)\otimes(A_Hy) + (A_Gx)\otimes(Iy) = \lambda x\otimes y
$$
due to $A_Hy=0$.
Hence
\begin{lemma}
\label{le-partial}
If $H$ has an eigenvalue~$0$,
then the spectrum of $G$ is contained in the spectrum of $G+_SH$ for each $S\subseteq V(G)$.
\end{lemma}
In addition, if $x$ and $y$ are $\pm 1$ vectors, then $x\otimes y$ is also a $\pm 1$ vector,
so that
\begin{corollary}
If $G$ and $H$ are eigenpartite graphs,
then $G+_SH$ is an eigenpartite graph for each $S\subseteq V(G)$.
\end{corollary}
Note that the construction showcased in Fig.~\ref{fig-4k} is
a partial Cartesian product of a graph~$G$ with the eigenvalue $\sqrt8$, with $S$ consisting of one of its leaves,
and a cycle $C_{4k}$, which has eigenvalue~$0$.
Hence by Lemma~\ref{le-partial},
the resulting partial Cartesian product has maximum degree three and the eigenvalue $\sqrt8$ for each $k\geq 1$.
\section{Conclusion}
We have studied here Wilf's question of what kind of a graph admits an eigenvector consisting solely of $\pm 1$ entries \cite{Wilf}?
Under Wilf's implicit assumption that the $\pm 1$ eigenvector should correspond to the smallest eigenvalue of a regular graph,
the question hardly has a simple answer,
due to the difference in behavior between the triangular graph $L(K_8)$ and the three Chang graphs,
all four being nonisomorphic strongly regular graphs with the same parameters $(28,12,6,4)$.
Without this assumption,
it turns out that to answer whether a graph has a $\pm 1$ eigenvector corresponding to any of its eigenvalues,
it is enough to be able just to answer whether a graph has a $\pm 1$ eigenvector corresponding to the eigenvalue~$0$.
This, unfortunately, does not make the situation any easier,
as the latter problem turns out to be NP complete.
Regardless of these negative results,
the set of graphs having a $\pm 1$ eigenvector corresponding to the eigenvalue~$0$ turns out to be quite rich:
it is closed under taking arbitrary NEPS and partial Cartesian products of its elements, and
for an arbitrary graph $G$ it contains a graph having $G$ as its induced subgraph.
\section*{Acknowledgements}
The author is grateful to Brendan McKay and L\'aszl\'o Lov\'asz for proving Theorem~\ref{th-laci},
and to Brendan McKay and Ross Kang for suggesting additional construction of eigenpartite graphs in Section~\ref{sc-constructions}.
\begin{thebibliography}{x}
\bibitem{Bare} E.H. Bareiss,
Sylvester's Identity and multistep integer-preserving Gaussian elimination,
\emph{Math. Comput.} \textbf{22} (1968), 565--578.
%\bibitem{BrHa} A.E. Brouwer, W.H. Haemers,
%Spectra of Graphs,
%Springer, New York, 2012.
\bibitem{Chan} L.-C. Chang,
The uniqueness and non-uniqueness of the triangular association schemes,
\emph{Science Rec. (Peking)} \textbf{3} (1959), 604--613.
\bibitem{Chan2} L.-C. Chang,
Association schemes of partially balanced block designs with parameters $\nu = 28$, $n_1 = 12$, $n_2 = 15$ and $p_{11}^2 = 4$,
\emph{Science Rec. (Peking)} \textbf{4} (1960), 12--18.
\bibitem{CvRS} D. Cvetkovi\'c, P. Rowlinson, S. Simi\'c,
Eigenspaces of graphs,
Cambridge University Press, Cambridge, 1997.
\bibitem{CvGu} D. Cvetkovi\'c, I. Gutman,
The algebraic multiplicity of the number zero in the spectrum of a bipartite graph,
{\em Mat. Vesn.} \textbf{9} (1972), 141--150.
\bibitem{Dias} J.R. Dias,
Structural origin of specific eigenvalues in chemical graphs of planar molecules,
\emph{Molec. Phys.} \textbf{85} (1995), 1043--1060.
\bibitem{FoSM} P.W. Fowler, D. Stevanovi\'c, M. Milo\v sevi\'c,
Counterexamples to a conjecture of Dias on eigenvalues of chemical graphs,
\emph{MATCH Commun. Math. Comput. Chem.} \textbf{63} (2010), 727--736.
\bibitem{GoMc} C.D. Godsil, B.D. McKay,
A new graph product and its spectrum,
\emph{Bull. Aust. Math. Soc.} \textbf{18} (1978), 21--28.
\bibitem{GuPo} I. Gutman, O.E. Polansky,
Mathematical concepts in organic chemistry,
Springer-Verlag, Berlin, 1986.
\bibitem{Hoff} A.J. Hoffman,
On the uniqueness of the triangular association scheme,
\emph{Ann. Math. Stat.} \textbf{31} (1960), 492--497.
\bibitem{Lova} L. Lov\'asz,
Coverings and colorings of hypergraphs,
Proc. 4th Southeastern Conf. on Combinatorics, Graph Theory, and Computing,
Utilitas Mathematica Publishing, Winnipeg, 1973, pp. 3--12.
\bibitem{MaMi} M. Marcus, H. Minc,
A survey of matrix theory and matrix inequalities,
Allyn and Bacon, Boston, 1964.
\bibitem{Stev} D. Stevanovi\'c,
Spectral radius of graphs,
Academic Press, Amsterdam, 2015.
\bibitem{TaVu} T. Tao, V. Vu,
Random matrices have simple spectrum,
preprint, arXiv:1412.1438v1 [math.PR].
\bibitem{Wilf} H.S. Wilf,
Spectral bounds for the clique and independence numbers of graphs,
\emph{J. Comb. Theory, Ser. B} \textbf{40} (1986), 113--117.
\bibitem{Yero} I.G. Yero,
Partial product of graphs and Vizing's conjecture,
\emph{Ars Math. Contemp.} \textbf{9} (2015), 19--25.
\end{thebibliography}
\end{document}