ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 11 (2016) 415-423
On ±1 eigenvectors of graphs
Dragan Stevanovic *
Mathematical Institute of the Serbian Academy of Science and Arts, Knez Mihajlova 36,11000 Belgrade, Serbia and University of Primorska, Institute Andrej Marusic, Muzejski trg 2, 6000 Koper, Slovenia
Received 30 January 2016, accepted 23 June 2016, published online 26 September 2016
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 ±1 entries? We prove that Wilf's problem is NP-complete, but also that the set of graphs having a ±1 eigenvector is quite rich, being closed under a number of different graph compositions.
Keywords: Eigenvector, adjacency matrix, Wilf's problem. Math. Subj. Class.: 05C50
1 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 n-conjugated hydrocarbon molecules, and their adjacency spectra provide models for energies of the n-molecular orbitals of such systems within the simple Hiickel approach (see, e.g., [10]). Restriction on the maximum vertex degree confines the eigenvalues of a chemical graph to the interval [-3, +3]. Jerry Ray Dias [6] noted that the examples of chemical graphs with adjacency eigenvalues 1, a/2, a/3, 2, a/5, a/6, a/7 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 a/8 and made an intriguing conjecture [6, §6] that no such graph exists. Together with Patrick Fowler and
*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 0N174033 of the Ministry of Education and Science of Serbia.
E-mail address: dragan.stevanovic@upr.si (Dragan Stevanovic)
Dedicated to the memory of Ante Graovac
Abstract
©® This work is licensed under http://creativecommons.Org/licenses/by/3.0/
416
Ars Math. Contemp. 11 (2016) 425-435
Figure 1: Construction of a graph with the maximum degree three and eigenvalue %/8 from 4k copies of smaller such graph containing a leaf. Copies of the local eigenvector corresponding to the eigenvalue %/8 are taken with the signs +, +, —, —, +, +, —, —,... to give an eigenvector corresponding to the eigenvalue %/8 in the larger graph. (Reprinted from [7].)
Marko Milosevic, the present author disproved Dias' conjecture by giving a number of constructions of chemical graphs with the eigenvalue %/8 in [7]. One particular construction, showcased in Fig. 1, 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 ±1 eigenvector corresponding to the adjacency eigenvalue 0.
Quite some time later, while meticulously preparing his research monograph on the spectral radius of graphs [14], the first author found out that Herbert Wilf had asked already in 1986 what kind of a graph admits an eigenvector consisting solely of ±1 entries? In Wilf's case, the question arised in the discussion of his spectral bound on the independence number of regular graphs [16]. Although the question explicitly asks just for a ±1 eigenvector of a graph, it is implicitly assumed in [16] 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 ±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 ±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 2 we prove that this problem is polynomially reducible to the problem of the existence of a ±1 eigenvector corresponding to the eigenvalue 0, and that the latter problem is NP-complete. In Section 3 we give a simple and straightforward algorithm for solving both problems, and use it to show that the three Chang graphs all have a ±1 eigenvector corresponding to the smallest eigenvalue, while L(K8), the fourth (28,12,6,4)-strongly regular graph, does not have such an eigenvector. Nevertheless, we show in Section 4 that the set of graphs with a ±1 eigenvector corresponding to the eigenvalue 0 has rich structure, being closed under a number of different graph compositions.
Cartesian product of two graphs Gi = (V\,E\) and G2 = (V2, E2) is the graph Gi + G2 with the vertex set Vi x V2 such that two vertices (u\, u2) and (v\, v2) are adjacent in Gi + G2 if either ui = vi, (u2, v2) G E2 or (ui, vi) G Ei, u2 = v2. Cartesian product of graphs is a special case of a more general graph composition, called the NEPS of graphs.
D. Stevanovic: On ±1 eigenvectors of graphs
417
Let B be a set of nonzero binary n-tuples, i.e., B C {0,1 }n \ {(0,..., 0}, such that for every
1	= 1,..., n there exists ft G B with ^ = 1. The non-complete extended p-sum of graphs G1 = (Vi, Ei),..., Gn = (Vn, En) with the basis B, denoted by NEPS(Gi,..., Gn; B), is the graph with the vertex set V1 x • • • x Vn in which two vertices u = (u1,..., un) and v = (v1,..., vn) are adjacent if and only if there exists ft G B such that for i = 1,..., n holds uj = vj if =0 and (uj, vj) G Ej if ^ = 1. The Kronecker product A ( B of matrices A = (ajj)m,n and B = (bjj)p,q is the mp x nq matrix obtained from A by replacing each entry ajj by the block ajj B. It is well known (see, e.g., [13]) that the Kronecker product is distributive with respect to the standard product of matrices:
(AB) ( (CD) = (A ( C)(B ( D).	(1.1)
2	NP-completeness of the existence of ± 1-eigenvectors
We start by showing that in order to be able to decide if the adjacency matrix of a graph has a ±1 eigenvector associated to an arbitrary eigenvalue, it is sufficient to know how to decide if the adjacency matrix has a ±1-eigenvector corresponding to the eigenvalue 0.
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.
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.
Theorem 2.1. PMEIG is polynomially reducible to PMEIG0.
Proof. Let G be an n-vertex simple graph with an adjacency matrix A. If G has a ±1 eigenvector x corresponding to some eigenvalue A of A, then from
Ax = Ax
and the fact that the entries of Ax and x are integers, we conclude that A must be an integer itself. (A cannot be a rational number as it is a root of the monic polynomial det(A1 - A) with integer coefficients.) The value |A| is bounded from above by the spectral radius A1(A) by the Perron-Frobenius theorem, which is further bounded from above by the maximum vertex degree A by the Rayleigh quotient (see, e.g., [14, pp. 8-11] for the discussion of the Perron-Frobenius theorem and the Rayleigh quotient). Thus,
A G {-A,..., A}.	(2.1)
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., [4, pp. 30-32]): if A is an eigenvalue of G with an eigenvector x and ^ is an eigenvalue of H with an eigenvector y, then A + ^ is the eigenvalue of G + H with the eigenvector x ( y, where ( 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 Km 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.
418
Ars Math. Contemp. 11 (2016) 425-435
Thus, if G has an integer eigenvalue A with a ±1 eigenvector x, then G +	has
an eigenvalue 0 with the corresponding ±1 eigenvector equal to either x ( j+ or x ( j -. We see that, due to (2.1), to solve PMEIG it is enough to solve PMEIG0 for the A +1 < n graphs
G, G + Ki,i, G + K2,2, ..., G + Ka,A.
Since these graphs have n, 2n, 4n, ..., 2An vertices, respectively, this represents a polynomial-time Turing reduction from PMEIG to PMEIG0.	□
Next, observe that each ±1 eigenvector x of A corresponding to the eigenvalue 0 determines the partition V = Vx+ U V- of the vertex set V of G:
V+ = {u e V : x„ = 1}, V- = {u e V : x„ = -1}.
Due to
Ax = 0
and the fact that for each u e V
(Ax)„ = ^ xv,	(2.2)
v^u
we see that the partition V + = V+, V- = V— satisfies:
For each vertex u e V the number of its neighbors in V+ is equal to the number of its neighbors in V-.
We will say that a graph G with the vertex set V is eigenpartite if there exists a partition V = V + U V-, V + n V- = 0, satisfying the property (2.3). From (2.2) it is obvious that if G is eigenpartite, then G has a ±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 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 Laszlo Lovasz.
Theorem 2.2. PMEIG0 is NP-complete.
Proof. We prove this theorem by reducing a known NP-complete problem to PMEIG0. For an integer k > 2, a 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 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 [12] that deciding 2-colorability of k-uniform hypergraphs is NP-complete for every fixed k > 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 U E' U E", where E' and E" are two copies of E:
E' = {e' : e e E}, E'' = {e'' : e e 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}.
D. Stevanovic: On ±1 eigenvectors of graphs
419
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' U 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 (2.3). 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 (2.3) 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.	□
3 An exhaustive search algorithm for PMEIG0
The eigenspace E0 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.
_ b
To compute the basis of E0 it thus suffices to compute the column echelon form
C
of
the row augmented matrix
During the computation of the column echelon form of A,
the identity matrix in
serves to keep track of the coefficients of linear combinations
of columns of A which yield the columns of B. Thus, the basis of E0 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 [1].
INPUT: An n x n adjacency matrix A
OUTPUT: A ±1-eigenvector x of the eigenvalue 0 of A, if it exists
Use Bareiss algorithm to compute the column echelon form
of
D ^ the nonzero columns of C such that the corresponding column of B is 0 if D is empty then
return "there is no such eigenvector" end if
k ^ the number of columns of D
U ^ the set of row indices of D yielding a submatrix E of rank k
for each z e {-1, +1}U do
solve the linear system Ey = z x ^ Dy
if x is a ±1 vector then
return x end if end for
return "there is no such eigenvector" The second part of the algorithm then exhaustively searches the set of all ±1 vectors over U for their potential extensions to the full ±1 eigenvector of the eigenvalue 0: any z € {-1, +1}U can be uniquely written as z = Ey, since E has the full rank, and then
420
Ars Math. Contemp. 11 (2016) 425-435
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 [15] of Babai's conjecture that the Erdos-Renyi random graph G(n, 2) 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 2.2 in the reduction from the problem of 2-coloring 4-uniform hypergraph H = (V, E) to PMEIG0, is bipartite with the bipartition (V, E' U E"). Multiplicity of its eigenvalue 0 is then, according to [5], 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 22|E|-|V 1.
The above algorithm can be used to test existence of a ±1 eigenvector for any other fixed eigenvalue A of the adjacency matrix A simply by supplying A - XI instead of A to it. We have run this algorithm on the triangular graph L(K8) and the three Chang graphs cospectral to it. Recall that the triangular graph is the line graph L(Km), 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 (v, k, A, p) = (m(m-1)/2,2(m-2), m-2,4). Chang [2, 3] and Hoffman [11] proved that if G is a strongly regular graph with these parameters, then for m = 8, m > 4, G is isomorphic to the triangular graph L(Km), while for m = 8, G is isomorphic either to L(K8) 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 ±1 eigenvector corresponding to the least eigenvalue -2, while the triangular graph L(K8) 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 ±1 eigenvector corresponding to the smallest eigenvalue of a regular graph.
4 Constructions of eigenpartite graphs
Although it is NP-complete to check whether a given graph is eigenpartite, sheer simplicity of its defining condition 2.3 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:
•	(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.
•	(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
D. Stevanovic: On ±1 eigenvectors of graphs
421
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
• (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 sp + m = sq = sr + 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
The set of eigenpartite graphs is, in addition, closed to taking arbitrary NEPS. Important property of NEPS(Gi,..., Gn; B) is that its spectrum can be represented by the spectra of G1,..., Gn [4, Theorem 2.3.4]: if Aj is an eigenvalue of Gj with the corresponding eigenvector x^ for i = 1,..., n, then
A= E A?1 ••• An"
pes
is the eigenvalue of NEPS(G1,..., Gn; B) with the corresponding eigenvector
x = xi ( ■ ■ ■ ( xn,
where ( denotes the Kronecker product of matrices. Thus, if each xj is a ±1 eigenvector corresponding to the eigenvalue 0 of Gj, then x = x1 ( ■ ■ ■ ( xn is a ±1 eigenvector corresponding to the eigenvalue 0 of NEPS(G1,..., Gn; B).
Many standard graph products are instances of NEPS: the Cartesian product of two graphs is obtained for the basis B = {(1,0), (0,1)}, the direct product for B = {(1,1)}, and the strong product for B = {(1,1), (1,0), (0,1)}.
The last construction we present here relies on partial Cartesian product of graphs [9]. Let G = (V, E) and H = (W, F) be two graphs. For S C V, the partial Cartesian product of G and H with respect to S is the graph G +S H with the vertex set V x W, with two vertices (v1, w1) and (v2, w2) adjacent if and only if either v1 = v2 G S and (w1, w2) G F or (v1, v2) G E and w1 = w2. If S = V then G+S H is just the standard Cartesian product G + H, while if S = {v} is a singleton, then G H is a particular case of the rooted product of graphs [8].
If Ag and Ah are adjacency matrices of G and H, respectively, then the adjacency matrix A of G +S H is given by
A = IS ( AH + AG ( I, where IS is the diagonal matrix defined as
1, if u = v € S,
(Is )u'v 1 0, otherwise,
422
Ars Math. Contemp. 11 (2016) 425-435
and I is the standard unit matrix. If x is an eigenvector corresponding to the eigenvalue A of G and y is an eigenvector corresponding to the eigenvalue 0 of H, then from (1.1)
A(x ( y) = (Isx) ( (Ahy) + (AGx) ( (Iy) = Ax ( y
due to Ah y = 0. Hence
Lemma 4.1. If H has an eigenvalue 0, then the spectrum of G is contained in the spectrum of G +S H for each S C V(G).
In addition, if x and y are ±1 vectors, then x ( y is also a ±1 vector, so that
Corollary 4.2. If G and H are eigenpartite graphs, then G +S H is an eigenpartite graph for each S C V(G).
Note that the construction showcased in Fig. 1 is a partial Cartesian product of a graph G with the eigenvalue %/8, with S consisting of one of its leaves, and a cycle C4k, which has eigenvalue 0. Hence by Lemma 4.1, the resulting partial Cartesian product has maximum degree three and the eigenvalue %/8 for each k > 1.
5 Conclusion
We have studied here Wilf's question of what kind of a graph admits an eigenvector consisting solely of ±1 entries [16]? Under Wilf's implicit assumption that the ±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(K8) 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 ±1 eigenvector corresponding to any of its eigenvalues, it is enough to be able just to answer whether a graph has a ±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 ±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.
Acknowledgements
The author is grateful to Brendan McKay and Laszlo Lovasz for proving Theorem 2.2, and to Brendan McKay and Ross Kang for suggesting additional constructions of eigenpartite graphs in Section 4.
References
[1]	E. H. Bareiss, Sylvester's Identity and Multistep Integer-Preserving Gaussian Elimination, Mathematics of Computation 22 (1968), 565-565, doi:10.2307/2004533.
[2]	L. Chang, The uniqueness and non-uniqueness of the triangular association schemes, Sci. Record, Math. New Ser. 3 (1959), 604-613.
[3]	L. Chang, Association schemes of partially balanced block designs with parameters v = 28, n1 = 12, n2 = 15 and p11 = 4, Sci. Record, Math. New Ser. 4 (1960), 12-18.
D. Stevanovic: On ±1 eigenvectors of graphs
423
[4]	D. CvetkoviC, P. Rowlinson and S. Simic, Eigenspaces of graphs, Cambridge: Cambridge University Press, 1997.
[5]	D. M. Cvetkovic and I. M. Gutman, The algebraic multiplicity of the number zero in the spectrum of a bipartite graph, Mat. Vesn., N. Ser. 9 (1972), 141-150.
[6]	J. R. Dias, Structural origin of specific eigenvalues in chemical graphs of planar molecules molecular orbital functional groups 85 (1995), 1043-1060, doi:10.1080/00268979500101651.
[7]	P. W. Fowler, D. Stevanovic and M. Milosevic, Counterexamples to a conjecture of Dias on eigenvalues of chemical graphs, MATCH Commun. Math. Comput. Chem. 63 (2010), 727-736.
[8]	C. Godsil and B. McKay, A new graph product and its spectrum, Bull. Aust. Math. Soc. 18 (1978), 21-28, doi:10.1017/S0004972700007760.
[9]	I. Gonzalez Yero, Partial product of graphs and Vizing's conjecture, Ars Math. Contemp. 9 (2015), 19-25.
[10]	I. Gutman and O. E. Polansky, Mathematical concepts in organic chemistry, Berlin etc.: Springer-Verlag. X, 212 p.; DM 128.00 (1986)., 1986.
[11]	A. Hoffman, On the uniqueness of the triangular association scheme, Ann. Math. Stat. 31 (1960), 492-497, doi:10.1214/aoms/1177705914.
[12]	L. Lovasz, Coverings and colorings of hypergraphs, Proc. 4th southeast. Conf. Comb., Graph Theor., Comput.; Boca Raton 1973, 3-12 (1973)., 1973.
[13]	M. Marcus and H. Minc, A survey of matrix theory and matrix inequalities, Boston: Allyn and Bacon, Inc. XVI, 180 p. (1964)., 1964.
[14]	D. Stevanovic, Spectral radius of graphs, Amsterdam: Elsevier/Academic Press, 2015.
[15]	T. Tao and V. Vu, Random matrices have simple spectrum, 2014, Submitted on 3 Dec 2014.
[16]	H. S. Wilf, Spectral bounds for the clique and independence numbers of graphs, J. Comb. Theory, Ser. B 40 (1986), 113-117, doi:10.1016/0095-8956(86)90069-9.