EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 10, No. 5, 2017, 1050-1057 ISSN 1307-5543 – www.ejpam.com Published by New York Business Global Nullity of Corona of a Path with Smith Graphs Usha Sharma1, Renu Naresh1,∗ 1 Department of Mathematics and Statistics, Banasthali University, Rajasthan 304022, India Abstract. Let G be a graph and A(G) be its adjacency matrix. The nullity of graph is the presence of zero as an eigenvalue in the spectrum of G. In this paper, we have established the results on nullity of (Pn � Sm) where Sm is smith graph and � is corona product. Moreover we have shown that nullity of (Pn � Sm) depends upon the nullity of Sm, which comes out to be a multiple of nullity of Sm. 2010 Mathematics Subject Classifications: 05C50 Key Words and Phrases: smith graphs, eigenvalue, nullity, corona product 1. Introduction and Preliminaries For all terminology and notations in graph theory and spectral graph theory not es- pecially defined in this paper, we refer the reader to the standard text books [4] and [1] respectively. By a graph we mean finite, simple, connected and undirected graph. The eigenvalues of a graph G is the eigenvalues of its adjacency matrix. The nullity of a graph G is the presence of zero as an eigenvalue in the spectrum of a graph G. It is denoted by η(G). Firstly we recall some basic definitions and existing results from [5]. A function f : V (G) → R where R is the set of real numbers, which assigns a weight (real number) to each vertex of G is called a vertex weighting of graph G. If there exist at least one vertex v ∈ V (G) for which f(v) 6= 0, then it is called non trivial weighting. A non-trivial vertex weighting of a graph G is called a zero-sum weighting of a graph G if for each v ∈ V (G), ∑ f(u) = 0, where ∑ is taken to all neighbor v. For any two non zero real number a and b the zero-sum weighting of a graph G is shown in Figure 1. The maximum number of non-zero independent variables used in a zero-sum weighting is called a high zero-sum weighting of the graph. ∗Corresponding author. Email addresses: usha.shrma94@yahoo.com (U. Sharma), renunaresh1@gmail.com (R. Naresh) http://www.ejpam.com 1050 c© 2017 EJPAM All rights reserved. U. Sharma, R. Naresh / Eur. J. Pure Appl. Math, 10 (5) (2017), 1050-1057 1051 0 a b -b -a -b a b -a Figure 1: G. In a high zero-sum weighting of G, the maximum number of non-zero independent variables is equal to the nullity of G. For a graph G, shown in Figure 1, we have used two non-zero independent variables a and b for high zero-sum weighting of G. In view of the above definition, we conclude that η(G) = 2. For a connected graph, two non-adjacent vertices are said to be co-neighbor vertices if they have same set of neighbors. Let G1 and G2 be two graphs with vertex set V (G1) = {v1, v2, . . . , vp1} and V (G2) = {u1, u2, . . . , up2}, respectively. Then, the corona of G1 and G2, denoted by G1 � G2 is defined as take one copy of G1 and p1 copies of G2 by adjoining ith vertex of G1 to each vertex of G2 in ith copy. The following Lemma is important in the study of nullity of a graph G and is known as co-neighbor lemma. Lemma 1. Let G be a connected graph and vi and vj be two co-neighbor vertices of G. Then, η(G) = η(G− vi) + 1 = η(G− vj) + 1. A graph is called smith if one of its eigenvalue is 2 and a smith graph on m vertices is denoted by Sm. Upto isomorphic, there are precisely 6 kinds of smith graphs namely Wm;m ≥ 6 (double head snake graph), Cm;m ≥ 3 (cycle graph), H7, H8, H9 and K1,4. From [2] except K1,4 other smith graphs (Wm;m ≥ 6, Cm;m ≥ 3, H7, H9) are extended form of Dynkin graphs (D̃m, Ãm, Ẽ6, Ẽ7) and H8 is Dynkin graph E8. The concept of nullity is very much applicable for the stability of unsaturated conjugate hydrocarbons molecules by Huckel molecular orbital theory (HMO) [3]. According to HMO theory, following two cases occurs: (i) If η(G) > 0, then the isomorphic chemical molecule is more reactive and unstable. U. Sharma, R. Naresh / Eur. J. Pure Appl. Math, 10 (5) (2017), 1050-1057 1052 (ii) If η(G) = 0, then the isomorphic chemical molecule is stable and less reactive. Motivated by the earlier study on the nullity of a graph. Here, we have determined the nullity of corona of a path with smith graphs. 2. Main Results In this section, we study the nullity of corona of a path with smith graphs. Lemma 2. For a smith graphs Sm, nullity is given by (i) η(Cm) = { 2, m ≡ 0 (mod 4) 0, otherwise (ii) η(Wm) = { 3, if m is odd 2, otherwise (iii) η(K1,4) = 3 (iv) η(H7) = 1 (v) η(H8) = 0 (vi) η(H9) = 1. Proof. We will prove the entire result by weighting technique. (i) Firstly we assume that Sm be Cm; m ≥ 3. There are two cases viz. m ≡ 0 (mod 4) and m 6≡ 0 (mod 4). For m ≡ 0 (mod 4), let xi be the weights of vertices of Cm. We have the following conditions ∑ w∈NCm (v) f(w) = 0, ∀ v ∈ V (Cm). U. Sharma, R. Naresh / Eur. J. Pure Appl. Math, 10 (5) (2017), 1050-1057 1053 On solving the equation we get x1 = x5 = . . . xm−3 = a1(say) x3 = x7 = · · · = xm−1 = −a1 and x2 = x6 = . . . xm−2 = a2(say) x4 = x8 = . . . xm = −a2. We have used two non-zero independent variables a1 and a2 in a zero-sum weighting of Cm. Therefore, η(Cm) = 2. For m 6≡ 0 (mod 4), we have used same procedure as above. After solving we get solution x1 = x2 = . . . xm = 0. Therefore, η(Cm) = 0. Hence, by the above two cases η(Cm) = { 2, m ≡ 0 (mod 4) 0, otherwise (ii) Let Sm to be Wm; m ≥ 6. We tackle following cases: Case (i) If m is even, then we have used two independent variables a1 6= 0, a2 6= 0 in a zero-sum weighting of Wm. Therefore, η(Wm) = 2. Case (ii) If m is odd, then we have used three non-zero independent variables in a zero-sum weighting of Wm. Therefore, η(Wm) = 3. Hence, η(Wm) = { 3, if m is odd 2, otherwise (iii) Let Sm to be isomorphic to K1,4. Let xi, ∀ i = 1, 2, . . . , 5 be the weights of vertices respectively. Then, we have following conditions∑ w∈NK1,4 (v) f(w) = 0, ∀ v ∈ V (K1,4). 5∑ i=2 xi = 0 and x1 = 0, ∀ xi; i = 2, 3, 4, 5. After solving these equations, we get x2 = a1, x3 = a2, x4 = a3 and x5 = −(a1 + a2 + a3). Here, we have used three non-zero independent variables in a zero-sum weighting of K1,4. Therefore, η(K1,4) = 3. U. Sharma, R. Naresh / Eur. J. Pure Appl. Math, 10 (5) (2017), 1050-1057 1054 (iv) Let us take Sm to be H7. In zero-sum weighting of H7, we have used only one non-zero independent variables. Therefore, η(H7) = 1. (v) We suppose that Sm be H8. We have not found the non-zero independent variables for zero-sum weighting of H8. Hence, η(H8) = 0. (vi) If we take Sm be H9, then we have used one non-zero independent variable in zero- sum weighting of H9. Hence, η(H9) = 1. � Theorem 1. Let Sm be any smith graph with m vertices and let η(Sm) denote the nullity of Sm. Then the nullity of smith graph Sm belongs to the set {0, 1, 2, 3}. Proof. The proof of the result can be given by Lemma 2. � Corollary 1. The converse of Theorem 2. does not hold in general, i.e. η(G) ∈ {0, 1, 2, 3} then G need not be a smith graph. As for instance, the nullity of both Pn and Kn ∈ (0, 1) however none of them is smith. Remark. It is interesting to note here that we can not have a graph as from [3] η(G) = n if and only if G is a null graph. Thus the following problem arises. Problem: For a given n, does there exist a graph of order p > n, such that η(G) = n. We answer to this problem in affirmative due to the following theorem: Theorem 2. Let (Pn � Sm) be the corona of a path with Sm, where Sm is H9. Then η(Pn � Sm) = n. Proof. Let us consider smith graph Sm to beH9 and let the vertices of Pn are v1, v2, v3, . . . vn and vertices of H9 are u1, u2, u3, . . . u9 in a usual manner as shown in Figure 2. The corona of Pn withH9 has vertex set V i(G) = {uij , vi : i = 1, 2, . . . , n, j = 1, 2, . . . , 9}. v v v u u u u u u 14 u15 u17 u1911 12 181613 u u u u u u 24 u u u2921 2622 23 25 27 28 u u u u u u n4 u u un1 n2 n3 n5 n6 n7 n8 n9 1 2 n Figure 2: (Pn �H9) Let xij and yi be weights of the vertices of (Pn �H9) as indicated in Figure 3. Then, ∑ w∈N(Pn�H9) (v) f(w) = 0, ∀ v ∈ V (Pn �H9). U. Sharma, R. Naresh / Eur. J. Pure Appl. Math, 10 (5) (2017), 1050-1057 1055 x x x x x x x x x x x x x x x x x x x x x x x x x x x y y y 11 12 13 14 15 16 17 18 19 21 22 23 24 25 26 27 28 29 n1 n2 n3 n5 n4 n6 n7 n8 n9 1 2 n Figure 3: (Pn �H9) These equations possess solution if and only if xnj = 0; j = 1, 2, 3, 6, 8 and xn4 = xn7 = a1;xn5 = xn9 = −a1. Clearly, we have used n independent variable in a zero-sum weighting of (Pn�H9). There- fore, η(Pn �H9) = n. Hence from the above discussion it is clear that η(Pn � Sm) = n, where Sm is H9. � Theorem 3. Let (Pn � Sm) denotes the corona of a path with Sm. Then η(Pn � Sm) ∈ {0, 2n, 3n}, where Sm is either Wm or K1,4 or Cm or H7 or H8. Proof. We will prove the entire result for each of the smith graph separately. First consider Sm to be Wm;m ≥ 6 to the vertices of (Pn � Sm). We need to tackle two cases for m, viz., m = 4k + 1 and m 6= 4k + 1 where k = 2, 3, . . . . Let m = 4k+1 on applying co-neighbor lemma. In this case, we have 2 pairs of co-neighbor vertices in each copy of Wm, it means that we have to remove 2 vertices in each copy of Wm. It implies that total 2n vertices have been removed from (Pn �Wm). Thus we get η(Pn �Wm) = η(Pn �W ′m) + 2n, where W ′m = Pm−2;m − 2 = 4k − 1 and k = 2, 3, . . . . Therefore, we conclude that η(Pn �Wm) = 3n. Next, let m 6= 4k+ 1, using the same procedure as above, we conclude that η(Pn�Wm) = 2n. Hence. We get η(Pn �Wm) = { 3n, m = 4k + 1, where k = 2, 3, . . . 2n, otherwise Consider Sm to be K1,4. The co-neighbor vertices of (Pn � K1,4) are (u2, u3), (u3, u4), (u4, u5) in each copy. On applying co-neighbor lemma, we remove three vertices from each copy. Then the nullity of (Pn �K1,4) = η(Pn �K2) + 3n. Hence, we conclude that η(Pn � K1,4) = 3n. Let Sm to be Cm. Here we need to tackle two cases for m, viz. m ≡ 0 (mod 4) and m 6≡ 0 (mod 4). Case (i). For m ≡ 0 (mod 4) we will find the nullity of (Pn � Cm). We assume that U. Sharma, R. Naresh / Eur. J. Pure Appl. Math, 10 (5) (2017), 1050-1057 1056 v v v u u u u u u u u u u u 12 13 14 15 22 23 24 n2 n3 n4 u25 un5 1 2 n 11 u21 un1 Figure 4: (Pn �K1,4) uij = xij and vi = yi be weighting of graph (Pn � Cm) , where ; i = 1, 2, . . . , n and j = 1, 2, . . . ,m. Then from ∑ w∈N(Pn�Cm)(v) f(w) = 0, ∀ v ∈ V (Pn � Cm). We get equations, and after solving these equations, we have used 2 non-zero variables in each copy of Cm. It means that we have to use 2n independent variables, for a zero- sum weighting of (Pn � Cm). Case (ii). For m 6≡ 0 (mod 4). We found that no non-zero independent variables in a zero-sum weighting of (Pn � Cm). From the above cases, we conclude that η(Pn � Cm) = { 2n, m ≡ 0 (mod 4) 0, m 6≡ 0 (mod 4) Finally, let Sm to be either H7 or H8 respectively. Using the procedure analogues as done in Theorem 2, we have used no independent variables in zero-sum weighting of (Pn �H7) and (Pn �H8). Therefore, nullity of both the graphs is zero. Therefore, η(Pn �H7) = 0 or η(Pn �H8) = 0. From the above analysis, it is clear that, η(Pn � Sm) ∈ {0, 2n, 3n}. � Theorem 4. Let (Pn�Sm) denotes the corona of a path with any smith graph Sm. Then η(Pn � Sm) ∈ {0, n, 2n, 3n}. Proof. The proof of the result can be given by Theorem 2 and Theorem 3. � Now we give the following result which established the connection between nullity of corona of Pn with Sm and nullity of Sm. REFERENCES 1057 Theorem 5. Let (Pn�Sm) denotes the corona of a path with smith graph Sm, where Sm is either K1,4 or Cm;m ≥ 3 or H8 or H9 or Wm, m = 4k+ 5 or m = 2k+ 4, k = 1, 2, 3, . . . . Then η(Pn � Sm) = n.η(Sm), where n is the order of path. Theorem 6. Let (Pn � Sm) denotes the corona of a path with smith graph Sm, where Sm is either H7 or Wm, m = 2k + 5, k = 1, 3, 5, . . . . Then η(Pn � Sm) = n.(η(Sm) − 1), where n is the order of path. Acknowledgements The authors would like to thank Dr. Pranjali (Banasthali University Rajasthan) for her thought suggestions to improve the provoking presentation of the paper. The authors are also thankful to anonymous referee for giving valuable comments. References [1] Cvetkovic, D. M., Doob, M., Sachs, H., Spectra of graphs. Theory and Applications, 1995. [2] Dokuchaev, Michael A., Gubareni, Nadiya M., Futorny, Vyacheslav M., Khibina, Marina A., Kirichenko, Vladimir, V., Dynkin diagrams and spectra of graphs, Sao Paulo Journal of Mathematical Sciences, 7 (1),83-104, 2013. [3] Gutman, I. and Borovicanin, B., Nullity of graphs: an Updated Survey. Zbornik Radona (Beograd), 14 (22), 137-154, 2011. [4] Harary, F., Graph Theory, Addison-Wesley Publ. Comp. Reading M. A.,(1969) [5] Sharaf, K. R. and Rasul, K. B., On the Nullity of Expanded Graphs, Gen. Math. Notes, 21(1), 97- 117, 2014.