An exposition on singular graphs: The cartesian product of two graphs

This paper is an exposition of the Singular graphs: The Cartesian Product of Two Graphs, from the study of Severino V. Gervacio. The adjacency matrix of agraph G with vertices V1, V2,...,Vn is the n x n matrix A(G) = [aij], where aij = 1 if Vi and Vj are adjacent, and aij = 0 otherwise. The graph G is said to be singular if A(G) i singular,i.e., det A(G) = 0 otherwise, G is said to be non-singular. The cartesian product of two graphs G and H, denoted by G x H, may be singular or non-singular, independently of the singularity or non-singularity of G and H. We show that det A(Kn0 = (-1) n-1 (n-1) and hence Kn is non-singular only when n-2. If G is any graph, we prove that G x Kn is singular if and only if 1 or (1-n) is an eigenvalue of A(G). In particular, we show that the cartesian product of Cm and Kn, n-4, is singular if and only if m=0 (mod 6). Also, for 1- n-3, we show that Cm x K1 is singular if and only if m = 0 (mod 4) or m = 0 (mod 6), Cm x K2 is singular if and only if m = 0 (mod 30 and Cm x K3 is singular if and only if m = 0 (mod 2). We also prove that det (A(Km x Kn)) = (-2) (m-1)(n-1)(m-2)n-1(n-2)m-1(m+n-2). As a corollary, Km x Kn is singular if and only m = 2 or n = 2