The determinant of the adjacency matrix of cycle-power graph C4n

Southeast-Asian J. of Sciences: Vol. 7, No 1 (2019) pp. 10-17 THE DETERMINANT OF THE ADJACENCY MATRIX OF CYCLE-POWER GRAPH C4n N. Adsawatithisakul1, W. Summart2 and D. Samana3 1 Department of Mathematics, Faculty of Science and Technology. Nakhonratchasima Rajabhat University. Nakhonratchasima 30000, Thailand. email: na.adsawatithisakul@gmail.com 2 General Education Affair Thonburi University Bangkok 10160, Thailand. email: numai6060@hotmail.com 3 Department of Mathematics, Faculty of Science King Mongkut’s Institute of Technology Ladkrabang Bangkok 10520, Thailand. email: dechasamana@hotmail.com Abstract Cycle-Power Graphs, Cdn is a graph that has n vertices and two vertices u and v are adjacent if and only if distance between u and v not greater than d. In this paper, we show that the determinant of the adjacency matrix of cycle-power graph C4n are as follows det(A(C4n)) = ⎧⎨ ⎩ 0 ; n ≡ 0, 2, 4, 6, 8 mod 10 8 ; n ≡ 1, 3, 7, 9 mod 10 128 ; n ≡ 5 mod 10. and the condition for the adjacency matrix of cycle-power graph Cdn is singular matrix. 1 Introduction Let G be a simple graph with vertex set V (G) = {v1, v2, ..., vn} and edge set E(G). The adjacency matrix A(G) of G is the matrix [aij]n×n where Key words: Determinant, Cycle-power graph, Adjacency matrix. 2010 AMS Mathematics classification: 05C50. 10 N. Adsawatithisakul, W. Summart and D. Samana 11 aij = { 1 ; if vi and vj are adjacent 0 ; otherwise. The determinant of adjacency matrix of G is det(A(G) and kth eigenvalues of the adjacency matrix is E(G; k) which are independent of the choice of vertices in adjacency matrix and are an invariant of G, respectively. In 1974 and In 1980, N. Biggs [3] and D.M. Cvetkovic et.al [5] have published about determinant of adjacency matrix of some graphs, such as Kn, Cn, Pn and Wn. In 2002, M. Doob [6] had found determinant of adjacency matrix of graph G(r, t). In 2009, A. Abdollahi [1] had found determinant of adjacency matrix of graphs. In 2011, B. Gyurov and J. Cloud [8] had found determinant of adjacency matrix of Pin-wheel graph. In 2014, N. Adsawatithisakul and D. Samana [2] had shown determinant of adjacency matrix of square cycle graph. Furthermore, there are studies of graph about some properties of determinant for example, S. Hu [10] and A. Abdollahi [1] have found that determinant of graph with exactly one cycle and exactly two cycle, respectively. Cycle-power, Cdn is a graph that has n vertices and distance each pair of vertex is less or equal d . For example, Figure 1: some cycle-power graphs Cdn Moreover, there are studies about cycle power graph such as, In[4] and [11] studied about the colouring in cycle power, Y.Hoa, C.Woo and P.Chen [9] construct the sandpile group in cycle power , D.Li and M.Liu [12] consider cycle power and their complements which satisfy Hadwiger’s conjecture. In this article, we focus d = 4 of cycle-power graph which determinant of cycle-power C4n can find by Proposition 1.1 and Theorem 1.2. Proposition 1.1. [3] Suppose that [0, a2, ..., an] is the first row of the adjacency matrix of a circulant graph G. Then the eigenvalues of graph G is denoted E(G; k), E(G; k) = n∑ j=1 ajz j−1 12 The Determinant of The Adjacency Matrix of... where z = e 2kπi n , k = 1, 2, ..., n. Cycle-power graph C4n is a circulant graph then eigenvalues of C4n is E(C4n; k) = z + z 2 + z3 + z4 + zn−4 + zn−3 + zn−2 + zn−1. (1.1) Determinant of a square matrix can be find by eigenvalue its as below. Theorem 1.2. [7] Let λ1, ..., λn be a eigenvalues of a square matrix A. Then det(A) = n∏ i=1 λi. Next, we present lemma that will be used in the proof of determinant of adjacency matrix of cycle-power graph C4n. 2 Main Results In this section, we proof about lemma and main theorem as follows. Lemma 2.1. Let n be an odd integer with n ≥ 10 and n ≡ 5 mod 10. Then n−1∏ k=1 (cos kπ n cos 2kπ n cos 5kπ n ) = 8−(n−1). Proof. It can be proved by n−1∏ k=1 (cos kπ n cos 2kπ n cos 5kπ n ) = n−1∏ k=1 sin 2kπn sin 4kπ n sin 10kπ n 2 sin kπn 2 sin 2kπ n 2 sin 5kπ n = 1 8n−1 ⎛ ⎝ ∏n−1 k=n+12 sin 2kπ n sin 4kπ n sin 10kπ n∏n−1 2 k=1 sin (2k−1)π n sin (4k−2)π n sin (10k−5)π n ⎞ ⎠ = 1 8n−1 ⎛ ⎝∏n−12k=1 sin (2k−1)πn sin (4k−2)πn sin (10k−5)πn∏n−1 2 k=1 sin (2k−1)π n sin (4k−2)π n sin (10k−5)π n ⎞ ⎠ = 8−(n−1). Lemma 2.2. Let q be a positive number. Then 2q∏ k=1 (cos kπ 10q + 5 cos 2kπ 10q + 5 cos 5kπ 10q + 5 ) 4q+1∏ k=2q+2 (cos kπ 10q + 5 cos 2kπ 10q + 5 cos 5kπ 10q + 5 ) 6q+2∏ k=4q+3 (cos kπ 10q + 5 cos 2kπ 10q + 5 cos 5kπ 10q + 5 ) 8q+3∏ k=6q+4 (cos kπ 10q + 5 cos 2kπ 10q + 5 cos 5kπ 10q + 5 ) 10q+4∏ k=8q+5 (cos kπ 10q + 5 cos 2kπ 10q + 5 cos 5kπ 10q + 5 ) = 8−10q (2.1) N. Adsawatithisakul, W. Summart and D. Samana 13 Proof. The left hand side of (2.1) is 2q∏ k=1 (cos kπ 10q + 5 cos 2kπ 10q + 5 cos 5kπ 10q + 5 ) 4q+1∏ k=2q+2 (cos kπ 10q + 5 cos 2kπ 10q + 5 cos 5kπ 10q + 5 ) 6q+2∏ k=4q+3 (cos kπ 10q + 5 cos 2kπ 10q + 5 cos 5kπ 10q + 5 ) 8q+3∏ k=6q+4 (cos kπ 10q + 5 cos 2kπ 10q + 5 cos 5kπ 10q + 5 ) 10q+4∏ k=8q+5 (cos kπ 10q + 5 cos 2kπ 10q + 5 cos 5kπ 10q + 5 ) = ⎛ ⎝ 2q∏ k=1 sin 2kπ 10q+5 sin 4kπ 10q+5 sin 10kπ 10q+5 2 sin kπ 10q+5 2 sin 2kπ 10q+5 2 sin 5kπ 10q+5 ⎞ ⎠ ⎛ ⎝ 4q+1∏ k=2q+2 sin 2kπ 10q+5 sin 4kπ 10q+5 sin 10kπ 10q+5 2 sin kπ 10q+5 2 sin 2kπ 10q+5 2 sin 5kπ 10q+5 ⎞ ⎠ ⎛ ⎝ 6q+2∏ k=4q+3 sin 2kπ 10q+5 sin 4kπ 10q+5 sin 10kπ 10q+5 2 sin kπ 10q+5 2 sin 2kπ 10q+5 2 sin 5kπ 10q+5 ⎞ ⎠ ⎛ ⎝ 8q+3∏ k=6q+4 sin 2kπ 10q+5 sin 4kπ 10q+5 sin 10kπ 10q+5 2 sin kπ 10q+5 2 sin 2kπ 10q+5 2 sin 5kπ 10q+5 ⎞ ⎠ ⎛ ⎝ 10q+4∏ k=8q+5 sin 2kπ 10q+5 sin 4kπ 10q+5 sin 10kπ 10q+5 2 sin kπ 10q+5 2 sin 2kπ 10q+5 2 sin 5kπ 10q+5 ⎞ ⎠ = 1 810q ⎛ ⎝∏qk=1 sin (2k−1)π10q+5 sin (4k−2)π10q+5 sin (10k−5)π10q+5∏q k=1 sin (2k−1)π 10q+5 sin (4k−2)π 10q+5 sin (10k−5)π 10q+5 ⎞ ⎠ ⎛ ⎝ ∏3q+1 k=2q+2 sin (2k−(2q+1))π 10q+5 sin (4k−(4q+2))π 10q+5 sin (10k−(10q+5))π 10q+5∏3q+1 k=2q+2 sin (2k−(2q+1))π 10q+5 sin (4k−(4q+2))π 10q+5 sin (10k−(10q+5))π 10q+5 ⎞ ⎠ ⎛ ⎝ ∏5q+2 k=4q+3 sin (2k−(4q+3))π 10q+5 sin (4k−(8q+6))π 10q+5 sin (10k−(20q+15))π 10q+5∏5q+2 k=4q+3 sin (2k−(4q+3))π 10q+5 sin (4k−(8q+6))π 10q+5 sin (10k−(20q+15))π 10q+5 ⎞ ⎠ ⎛ ⎝ ∏7q+3 k=6q+4 sin (2k−(6q+3))π 10q+5 sin (4k−(12q+6))π 10q+5 sin (10k−(30q+15))π 10q+5∏7q+3 k=6q+4 sin (2k−(6q+3))π 10q+5 sin (4k−(12q+6))π 10q+5 sin (10k−(30q+15))π 10q+5 ⎞ ⎠ ⎛ ⎝ ∏9q+4 k=8q+5 sin (2k−(8q+5))π 10q+5 sin (4k−(16q+10))π 10q+5 sin (10k−(40q+25))π 10q+5∏9q+4 k=8q+5 sin (2k−(8q+5))π 10q+5 sin (4k−(16q+10))π 10q+5 sin (10k−(40q+25))π 10q+5 ⎞ ⎠ = 8−10q Next, we use Lemma 2.1 and 2.2 to find determinant of adjacency matrix of cycle-power graph C4n. 14 The Determinant of The Adjacency Matrix of... Theorem 2.3. Let C4n be a cycle-power graph with n vertices. Then det(A(C4n)) = ⎧⎨ ⎩ 0 ; n ≡ 0, 2, 4, 6, 8mod 10 8 ; n ≡ 1, 3, 7, 9 mod 10 128 ; n ≡ 5 mod 10. Proof. Let E(C4n; k) be a k th eigenvalue of adjacency matrix of cycle-power graph C4n. From (1.1), We get E(C4n;k) = e 2kπi n + e 4kπi n + e 6kπi n + e 8kπi n + e 2k(n−4)πi n + e 2k(n−3)πi n + e 2k(n−2)πi n + e 2k(n−1)πi n = e 2kπi n + e 4kπi n + e 6kπi n + e 8kπi n + e 2knπi n · e−8kπin + e 2knπin · e−6kπin + e 2knπin · e−4kπin + e 2knπi n · e−2kπin . By Euler’s formula, we obtain E(C4n; k) = (cos 2kπ n + i sin 2kπ n ) + (cos 4kπ n + i sin 4kπ n ) + (cos 6kπ n + i sin 6kπ n ) + (cos 8kπ n + i sin 8kπ n ) + (cos −8kπ n + i sin −8kπ n ) + (cos −6kπ n + i sin −6kπ n ) + (cos −4kπ n + i sin −4kπ n ) + (cos −2kπ n + i sin −2kπ n ) = 2 cos 2kπ n + 2 cos 4kπ n + 2 cos 6kπ n + 2 cos 8kπ n . We can rewrite E(C4n; k) = 8(cos kπ n cos 2kπ n cos 5kπ n ). (2.2) From (2.2), we have det(A(C4n)) = n∏ k=1 E(C4n; k) = n∏ k=1 8(cos kπ n cos 2kπ n cos 5kπ n ). (2.3) Consider n as follows, Case I, n ≡ 0, 2, 4, 6, 8mod 10. Since 1 ≤ k ≤ n and consider (2.2) when k = n 2 . Then E(C4n; n 2 ) = 8(cos π 2 cosπ cos 5π 2 ) = 0. N. Adsawatithisakul, W. Summart and D. Samana 15 From (2.3), we obtain det(A(C4n)) = n∏ k=1 E(C4n; k) = 0. Therefore, det(A(C4n)) = 0 when n ≡ 0, 2, 4, 6, 8mod 10. Case II, n ≡ 1, 3, 7, 9 mod 10. Since n is odd and n ≡ 5 mod 10. Then det(A(C4n)) = n∏ k=1 E(C4n; k) = n∏ k=1 8(cos kπ n cos 2kπ n cos 5kπ n ) = 8(cos nπ n cos 2nπ n cos 5nπ n )8n−1 n−1∏ k=1 (cos kπ n cos 2kπ n cos 5kπ n ) Using Lemma 2.1, we have det(A(C4n)) = n∏ k=1 E(C4n; k) = 8 · (8n−1) · (8−(n−1)) = 8 Therefore det(A(C4n)) = 8 when n is odd and n ≡ 5 mod 10. Case III, n ≡ 5 mod 10. Then n = 10q + 5, ∃q ∈ Z+. From (2.3), we obtain det(A(C4n)) = n∏ k=1 E(C4n; k) = 10q+5∏ k=1 8(cos kπ 10q+ 5 cos 2kπ 10q + 5 cos 5kπ 10q + 5 ) = 8(cos (2q + 1)π 10q+ 5 cos 2(2q + 1)π 10q + 5 cos 5(2q + 1)π 10q + 5 ) 8(cos (4q + 2)π 10q+ 5 cos 2(4q + 2)π 10q + 5 cos 5(4q + 2)π 10q + 5 ) 8(cos (6q + 3)π 10q+ 5 cos 2(6q + 3)π 10q + 5 cos 5(6q + 3)π 10q + 5 ) 8(cos (8q + 4)π 10q+ 5 cos 2(8q + 4)π 10q + 5 cos 5(8q + 4)π 10q + 5 ) 8(cos (10q + 5)π 10q + 5 cos 2(10q + 5)π 10q + 5 cos 5(10q+ 5)π 10q + 5 ) 16 The Determinant of The Adjacency Matrix of... 810q 2q∏ k=1 (cos kπ 10q + 5 cos 2kπ 10q + 5 cos 5kπ 10q + 5 ) 4q+1∏ k=2q+2 (cos kπ 10q + 5 cos 2kπ 10q + 5 cos 5kπ 10q+ 5 ) 6q+2∏ k=4q+3 (cos kπ 10q + 5 cos 2kπ 10q + 5 cos 5kπ 10q+ 5 ) 8q+3∏ k=6q+4 (cos kπ 10q + 5 cos 2kπ 10q + 5 cos 5kπ 10q+ 5 ) 10q+4∏ k=8q+5 (cos kπ 10q + 5 cos 2kπ 10q + 5 cos 5kπ 10q+ 5 ) = (−2)(−2)(−2)(−2)(8)(810q) 2q∏ k=1 (cos kπ 10q + 5 cos 2kπ 10q + 5 cos 5kπ 10q + 5 ) 4q+1∏ k=2q+2 (cos kπ 10q + 5 cos 2kπ 10q + 5 cos 5kπ 10q+ 5 ) 6q+2∏ k=4q+3 (cos kπ 10q + 5 cos 2kπ 10q + 5 cos 5kπ 10q+ 5 ) 8q+3∏ k=6q+4 (cos kπ 10q + 5 cos 2kπ 10q + 5 cos 5kπ 10q+ 5 ) 10q+4∏ k=8q+5 (cos kπ 10q + 5 cos 2kπ 10q + 5 cos 5kπ 10q+ 5 ). Using Lemma 2.2, we have det(A(C4n)) = (−2)(−2)(−2)(−2)(8)(810q)(8−10q) = 128 Therefore det(A(C4n)) = 128 when n ≡ 5 mod 10. From case I, II and III, then det(A(C4n)) = ⎧⎨ ⎩ 0 ; n ≡ 0, 2, 4, 6, 8mod 10 8 ; n ≡ 1, 3, 7, 9 mod 10 128 ; n ≡ 5 mod 10. Moreover, observe that det(A(Cdn)) = 0 where n = 2 + 2d and d are even, we have Corollary 2.4. N. Adsawatithisakul, W. Summart and D. Samana 17 Corollary 2.4. If n = 2 + 2d and d is even then the adjacency matrix of cycle-power graph Cdn is singular . Proof. Let d be even. By proposition 1.1, we have E(Cdn; k) = z + z 2 + . . .+ zd + zn−d + . . .+ zn−2 + zn−1 = 2 cos 2kπ n + 2 cos 4kπ n + . . .+ 2 cos 2kdπ n = 2 d∑ j=1 cos 2jkπ n (5) Since n = 2 + 2d and 1 ≤ k ≤ n. Consider (5) when k = n2 . Then E(Cdn; n 2 ) = 2 cos 2(n2 )π n + 2 cos 4(n2 )π n + . . .+ 2 cos 2(n2 )dπ n = 0. Therefore the adjacency matrix of Cdn is singular matrix. References [1] A. Abdollahi, Determinant of adjacency matrices of graph, Cornell University. [2] N. Adsawatithisakul and D. Samana, Determinant of adjacency matrix of square cycle graph, International Journal of Pure and Applied Mathematics, 2014. [3] N. Biggs,Algebraic Graph Theory, Cambridge University Press, Cambridge, 1974. [4] C.N. Campos and C.P. De Mello, A result on the total colouring of powers of cycles, Electronic Notes in Discrete Mathematics, 18, 2004, 47-52. [5] D.M. Cvetkovic, M. Doob and H. Sachs, Spectra of Graphs: Theory and Application, Academic Press, New York, 1980. [6] M. Doob, Circulant graphs with det(−A(G)) = −deg(G) :codeterminants with Kn,Linear Algebra Appl, 340, 2002, 87-96. [7] L. Goldberg, Matrix Theory with Applications, McGraw - Hill International Editions, Mathematics and Statistics Series, 1991. [8] B. Gyurov and J. Cloud, On the algebraic properties of Pin-Wheel graphs and Appli- cations, 73rd annual meeting of the Oklahoma Arkansas section 2011, University of central Oklahoma. [9] Y. Hoa, C. Woo and P. Chen, On the sandpile group of the square cycle C2n, Linear Algebra Appl, 418, 2006, 457-467. [10] S. Hu, The Classification and maximum determinants of the adjacency matrices of graphs with one cycle, J. Math. Study, 36, 2003, 102-104. [11] M. Krivelevich and A. Nachmias, Colouring powers of cycles from random lists, Euro- pean Journal of Combinatorics, 25, 2004, 961-968. [12] D.Li and M.Liu,Hadwiger’s conjecture for powers of cycles and their comple- ments,European Journal of Combinatorics, 28, 2007, 1152-1155.