The Nullity Of Tricyclic Graphs

The nullity of a graph is the multiplicity of the eigenvalue zero in its spectrum. Therehave been some very attractive results about the nullity of graphs in bipartite graphs, trees,line graphs of trees, unicyclic graphs and bicyclic graphs. In this paper, according to theclassification of bicyclic graphs, We give a classification to a new graph named tricyclicgraphs, and obtain the range of the nullity on the tricyclic graphs, and prove the existence ofthe nullity set about the tricyclic graphs.The first part is named Introduction. It reports the reality of researching and developingabout the nullity of graphs for recent years.The second part is named Preliminary knowledge. It includes some concepts related tograph and some lemmas respect to the nullity of graphs proved by others.The third part is named Definition and classification on the tricyclic graphs. If a sim-ple connected graph satisfies the condition that the number of edges equals the number ofvertices plus two, then the graph is called tricyclic graph. Denoted by CT_n the set of alltricyclic graphs of order n. Tricyclic graphs are partitioned off four great classes graphs,they are named C1T - graph,C2T - graph,C3T - graph and C4T - graph, respectively.And they are partitioned off fourteen little classes graphs, they are named C_1aT_n, C_1bT_n,C_1cT_n; C_2aT_n, C_2bT_n, C_2cT_n, C_2dT_n; C_3aT_n, C_3bT_n, C3cT_n,C_3dT_n, C_3eT_n; C_4aT_n and C_4bT_n,respectively.The fourth part is named The range of the nullity on the tricyclic graphs. Correspondingevery little class tricyclic graphs, We obtain the range of the nullity about the tricyclic graphswith n vertices. The main results is achieved as follows:Lemma4.1 Let G be a graph with n vertices, v_i∈V (G) and v_j∈V (G), if N(v_i) =N(v_j), thenη(G) = 1 +η(G - {v_i}).Lemma4.2 Let Ck,Cl be two vertex-joint cycles in G shown in Fig.4.1.1, and at leastone of k and l be greater than or equal to 5. Then r(A(G))≥8.Lemma4.3 Let G be a tricyclic graph shown in Fig.4.1.2, thenη(G) = 0.Theorem4.4 For any tricyclic graph G∈C_1aT_n (n≥11),η(G)≤n - 8.Lemma4.6 Let G be Hi(i = 1, 2, 3) shown in Fig.4.2.2, and k≥5, then r(A(G))≥9.Theorem4.7 For any tricyclic graph G∈C_1bT_n (n≥9),η(G)≤n - 8.Lemma4.9 Let G be a tricyclic graph with n vertices shown in Fig.4.3.3, and at leastone of k,l,m is greater than or equal to 5, then r(A(G))≥8.Theorem4.10 For any tricyclic graph G∈C_1cT_n (n≥10),η(G)≤n - 8.Theorem4.12 For any tricyclic graph G∈C_2aT_n (n≥13),η(G)≤n - 8.Theorem4.14 For any tricyclic graph G∈C_2bT_n (n≥10),η(G)≤n - 8. Theorem4.16 For any tricyclic graph G∈C_2cT_n (n≥9),η(G)≤n - 8.Theorem4.17 For any tricyclic graph G∈C_2dT_n (n≥11),η(G)≤n - 7.Theorem4.18 For any tricyclic graph G∈C_3aT_n (n≥9),η(G)≤n - 4.Theorem4.19 For any tricyclic graph G∈C_3bT_n (n≥10),η(G)≤n - 6.Theorem4.20 For any tricyclic graph G∈C_3cT_n (n≥9),η(G)≤n - 6.Theorem4.21 For any tricyclic graph G∈C_3dT_n (n≥9),η(G)≤n - 6.Theorem4.23 For any tricyclic graph G∈C_3eT_n (n≥9),η(G)≤n - 6.Theorem4.24 For any tricyclic graph G∈C_4aT_n (n≥7),η(G)≤n - 4.Theorem4.25 For any tricyclic graph G∈C_4bT_n (n≥8),η(G)≤n - 4.The fifth part is named The nullity set of the tricyclic graphs. Corresponding every littleclass tricyclic graphs, We prove the existence of the nullity set on the tricyclic graphs with nvertices. The main results is achieved as follows:Theorem5.1 The nullity set of C_1aT_n (n≥11) is [0,n - 8].Theorem5.2 The nullity set of C_1bT_n (n≥9) is [0,n - 8].Theorem5.3 The nullity set of C_1cT_n (n≥10) is [0,n - 8].Theorem5.4 The nullity set of C_2aT_n (n≥13) is [0,n - 8].Theorem5.5 The nullity set of C_2bT_n (n≥10) is [0,n - 8].Theorem5.6 The nullity set of C_2cT_n (n≥9) is [0,n - 8].Lemma5.7 Let G be a tricyclic graph shown in Fig.5.7, thenη(G) = 0.Theorem5.8 The nullity set of C_2dT_n (n≥11) is [0,n - 7].Lemma5.9 Let H1 be a tricyclic graph shown in Fig.5.9, thenη(H₁) = 0.Theorem5.10 The nullity set of C_3aT_n (n≥9) is [0,n - 4].Theorem5.11 The nullity set of C_3bT_n (n≥10) is [0,n - 6].Theorem5.12 The nullity set of C_3cT_n (n≥9) is [0,n - 6].Theorem5.13 The nullity set of C_3dT_n (n≥9) is [0,n - 6].Theorem5.14 The nullity set of C_3eT_n (n≥9) is [0,n - 6].Theorem5.15 The nullity set of C_4aT_n (n≥7) is [0,n - 4].Theorem5.16 The nullity set of C_4bT_n (n≥8) is [0,n - 4].