THE DETERMINANT OF THE WHEEL GRAPH AND CONJECTURES BY YONG

Iyad T. Abu-Jeib

Abstract. We prove that the determinant of the adjacency matrix of the wheel graph of even order is equal to the determinant of the adjacency matrix of the complete graph of the same order. We present counterexamples to two conjectures by Yong about simple undirected graphs.

1. Introduction. In this paper, the word graph refers to a simple undirected graph. We use K_{n} to refer to the complete graph on n vertices, C_{n} to refer to the cycle on n vertices (n ≥ 3), and W_{n} to refer to the wheel on n vertices (n ≥ 4). We recall that W_{n} = C_{n−1} + K_{1}. We denote the complement of a graph G by \overline{G} and the adjacency matrix of G by A(G). By writing G_{n}, we are denoting a graph having n vertices.

Yong [7] proposed three conjectures about graphs. The first is:

\underline{C1}. The graph G_{n} is complete if and only if det(A(G_{n})) = (−1)^{n−1}(n− 1).

While Olesky, Driessche, and Verner [4] have disproved this conjecture, their paper focused on finding a non-complete graph whose determinant is equal to det(A(K_{n})). This paper demonstrates that det(A(K_{n})) = det(A(W_{n})) for n even and 4 or larger, thereby providing (for n even and greater than 4) a family of counterexamples to C1.

Jinsong Tam [1] noticed that Yong’s second conjecture follows from a theorem by Collatz-Singowitz. Yong’s third conjecture is:

\underline{C3}. Let n ≥ 4, and let λ_{m}(G_{n}) be the m-th largest eigenvalue of G_{n}. Then λ_{k}(G_{n}) = −1 for 2 ≤ k ≤ [n/2] implies that λ_{j}(G_{n}) = −1, for k ≤ j ≤ n − k + 2.

Stevanovic [6] disproved C3 using graphs having 9 vertices. Here, using C_{n} and K_{n} we provide new counterexamples to C3 by constructing a family of graphs for which the number of vertices is not restricted.

As an aid to forthcoming calculations, we assume the vertices of C_{n} are labeled as v_{1}, v_{2}, …, v_{n} with v_{k} adjacent to v_{k+1} for 1 ≤ k ≤ n − 1 and with v_{n} adjacent to v_{1}. We assume the vertices of W_{n} are labeled as v_{1}, v_{2}, …, v_{n} with v_{k} adjacent to v_{k+1} for 2 ≤ k ≤ n − 1, with v_{n} adjacent to v_{2}, and with v_{1} adjacent to all other vertices.

2. The Wheel Graph and Yong’s First Conjecture. The cycle graph C_{n} has the following properties [2, 3]:

Since A(C_{n}) is circulant, then its eigenvalues are given by λ_{k} = e^{2πki/n} + e^{2(n−1)πki/n}, k = 1, …, n, where i = \sqrt{−1}. In particular, 2 is the largest eigenvalue of A(C_{n}). The n × 1 constant vector of 1’s is a corresponding eigenvector. For every eigenvector corresponding to any other eigenvalue, the sum of the entries of the eigenvector is zero. If n is odd, then every eigenvalue is repeated except the eigenvalue 2, and the product of the eigenvalues except the eigenvalue 2 is equal to 1. When n is even, -2 is the smallest eigenvalue of A(C_{n}). In this case, every eigenvalue of A(C_{n}) is repeated except the eigenvalues 2 and -2, and, for n mod 4 not zero, the product of the eigenvalues, except for 2 and -2, is 1. If n mod 4 is zero, then A(C_{n}) is singular.

\underline{Theorem 2.1}. Let n ≥ 4,

α = \frac{1 + \sqrt{n}}{n − 1}, β = \frac{1 − \sqrt{n}}{n − 1}, a = [ 1 ; α ; α ; ⋮ ; α ] , and b = [ 1 ; β ; β ; ⋮ ; β ] .

Then, the eigenvalues of A(W_{n}) are 1±\sqrt{n} together with the eigenvalues of A(C_{n−1}) except the eigenvalue 2. Moreover, a is an eigenvector of A(W_{n}) corresponding to the eigenvalue 1 + \sqrt{n} and b is an eigenvector of A(W_{n}) corresponding to the eigenvalue 1 − \sqrt{n}. Also, if v is an eigenvector of A(C_{n−1}) corresponding to the eigenvalue λ, where λ is any one of the n − 2 eigenvalues shared by A(C_{n−1}) and A(W_{n}), then

[ \begin{matrix}0 \\ v \end{matrix} ]

is an eigenvector of A(W_{n}) corresponding to the eigenvalue λ.

\underline{Proof}. Let m = n − 1. Then, it is easy to verify that (1 + \sqrt{n}, a) and (1 − \sqrt{n}, b) are eigenpairs of A(W_{n}). Now note that for any eigenvector of A(C_{n−1}) corresponding to an eigenvalue different than 2, the sum of the entries of the eigenvector is 0. Let (λ, v) be an eigenpair of A(C_{n−1}) where λ ≠ 2 and let

z = [ \begin{matrix}0 \\ v \end{matrix} ] .

When we multiply the first row of A(W_{n}) with z we get ∑_{k=1}^{n−1} v_{k} which is zero. The product of row k, k ≠ 1, of A(W_{n}) with z is equal to the product of row k − 1 of A(C_{n−1}) with v. Thus, A(W_{n})z = λz. Since the eigenvectors of A(C_{n−1}) are known, then those n−2 eigenvectors of A(W_{n}) are known.

The facts in the above theorem can also be found in [5]. However, unlike [5], we depended in the proof of the theorem on the fact that the eigen structure of the adjacency matrix of the cycle graph is known because it is circulant. We note that determinants were not discussed in [5].

Note that the eigenvalues of A(W_{n}) are 1 + \sqrt{n}, 1 − \sqrt{n}, e^{2πki/m} + e^{2(m−1)πki/m}, k = 1, …, m − 1, where m = n − 1. Thus, A(C_{n−1}) and A(W_{n}) share n − 2 eigenvalues, and n − 2 of the eigenvectors of A(W_{n}) can be obtained from n − 2 eigenvectors of A(C_{n−1}). In the following corollary, we use the eigenvalues of the adjacency matrix of the cycle graph to find the determinant of the adjacency matrix of the wheel graph.

\underline{Corollary 2.2}. Let n ≥ 4. Then

det(A(W_{n})) = \{ \begin{matrix}2(n − 1), & if n mod 4 is 3 \\ 0, & if n mod 4 is 1 \\ 1 − n, & if n mod 4 is 2 or 0. \end{matrix}

\underline{Proof}. Let m = n − 1. If n is even, then m is odd, and hence, the product of the eigenvalues of A(C_{m}) except the eigenvalue 2 is 1. Therefore, the product of the eigenvalues of A(W_{n}) except the eigenvalues 1 + \sqrt{n} and 1 − \sqrt{n} is 1. Hence, det(A(W_{n})) = 1 − n. Now if n is odd, then m is even, and hence, the product of the eigenvalues of A(C_{m}) except the eigenvalue 2 is -2 if m mod 4 is 2 and the product is 0 if m mod 4 is 0. Therefore, the product of the eigenvalues of A(W_{n}) except the eigenvalues 1 + \sqrt{n} and 1 − \sqrt{n} is -2 if n mod 4 is 3 and the product is 0 if n mod 4 is 1.

Thus, if n is an even integer greater than 2, then det(A(W_{n})) = det(A(K_{n})). Therefore, any member of the family {W_{n} | n ∈ 2ℤ, n > 4} provides a counterexample to Yong’s first conjecture.

3. Yong’s Third Conjecture. We present new counterexamples to C3. Unlike the graphs mentioned in [6], the graphs we present are not restricted to a limited number of vertices. Let

M = [ \begin{matrix}A(K_{15}) & A(\overline{C_{15}}) \\ A(\overline{C_{15}}) & A(C_{15}) \end{matrix} ] .

Then the eigenvalues of M are: 21.41641, 3.57433, 3.57433, 2.78339, 2.78339, 1.61803, 1.61803, 0.27977, 0.27977, -0.40898, -0.40898, -0.61803, -0.61803, -1.00000, -1.00000, -1.00000, -1.00000, -1.48883, -1.48883, - 2.00000, -2.00000, -2.00000, -2.00000, -2.44512, -2.44512, -2.54732, -2.54732, -2.74724, -2.74724, -5.41641. Now let G be the graph whose adjacency matrix is M. Taking k = 14 in the conjecture, implies n−k+2 = 18. According to the conjecture, λ_{j}(G), j = 14, …, 18, must be -1. Clearly, this is not the case, since λ_{18}(G) ≠ −1. Note that it is easy to verify (e.g. by Gaussian Elimination) that the rank of M +I, where I is the identity matrix of order 30, is 26. Note also that G is connected since the first vertex is adjacent to all other vertices except vertices 16, 17, and 30. But, vertex 1 is adjacent to vertex 4 which is adjacent to vertices 16, 17, and 30.

Apparently, if m ∈ 3ℤ^{+} and m ≥ 9, then every graph G whose adjacency matrix is

M = [ \begin{matrix}A(K_{m}) & A(\overline{C_{m}}) \\ A(\overline{C_{m}}) & A(C_{m}) \end{matrix} ] ,

provides a counterexample to C3. We observed that for such values of m, λ_{j}(G) = −1 for j = m−1, m, m+1, m+2, and the rank of I +M is 2m−4, where I is the identity matrix of order 2m.

\underline{References}

1. R. A. Brualdi, “From the Editor-in-Chief. Comment on: ‘On the Distribution of Eigenvalues of a Simple Undirected Graph,’ ” Linear Algebra Appl., 320 (2000), 214.

2. P. J. Davis, Circulant Matrices, Wiley Interscience, New York, NY, 1979.

3. P. Lancaster, Theory of Matrices, Academic Press, New York, NY, 1969.

4. D. D. Olesky, P. van den Driessche, and J. H. Verner, “Graphs With the Same Determinant as a Complete Graph,” Linear Algebra Appl., 312 (2000), 191–195.

5. A. J. Schwenk, “Computing the Characteristic Polynomial of a Graph,” Graphs and Combinatorics (R. Bari and F. Haray, eds.) Springer-Verlag, Berlin, 1974, 153–172.

6. D. Stevanovic, “Remarks on Graphs With Majority of Eigenvalues at Most -1,” Linear Algebra Appl., 367 (2003), 337–340.

7. X. R. Yong, “On the Distribution of Eigenvalues of a Simple Undirected Graph,” Linear Algebra Appl., 295 (1999), 73–80.

Mathematics Subject Classification (2000): 05C50

Iyad T. Abu-Jeib Department of Computer Science and Information Systems Fenton Hall SUNY Fredonia Fredonia, NY 14063 email: abu-jeib@cs.fredonia.edu