Change in the Nullity of a Graph Due to Some Operations
Keywords:Graph theory, high zero sum weighting, adjacency matrix, nullity, vertex identification
Two adjacent or non-adjacent vertices of a graph G are said to be identified, if they are combined to form one vertex whose neighbor is the union of their neighborhoods (ignoring any loops or multiple edges formed). The nullity of a graph G, denoted by η(G), is the multiplicity of the eigenvalue zero in its spectrum. A graph is a nullity critical if identifying any pair of vertices decreases or increases the nullity. On the other hand, a graph is a nullity- stable if identifying any pair of distinct vertices leaves the nullity unchanged. It is proved that in general, identifying any pair of distinct vertices cannot increase or decrease the nullity by at most 2. Also, nut graphs are constructed from old ones with smaller order and larger maximum degree. Our main tools to obtain such results are the interlacing theorem, the end vertex Lemma, the assignment of appropriate weights to the vertices which are going to be identified in a high zero sum weighting of the graph. The distance between vertices with the same weight plays an important role in the study of the change in the nullity on vertex identification in a graph.
Ali, D.A., Gauci, J.B., Sciriha, I., & Sharaf, K.R. (2016). Coalescence Fiedler and Core Vertices.
In: Czechoslovak Mathematical Journal, 66.141, 971–985.
Ali, D.A., Gauci, J.B., Sciriha, I., & Sharaf,
K.R. (2016). Nullity of a Graph with a Cut-Edge. Communication in Mathematical and in Computer Chemistry, 76, 771–791.
Brown, M., Kennedy, J.W., & Servatius, B. (1993).
Graph singularity. Graph Theory Notes of New York, 25, 23–32.
Cheng, B., & Liu, B. (2007). On the Nullity of Graphs. J. of linear Algebra, Volume, 16, 60-67.
Cvetkovic, D. M., Doob, M., & Sachs, H. (2009).
Spectra of graph theory and application. Academic Press, New York.
Omidi, G. R., (2007). On the Nullity of Bipartite
Graphs. Graphs and Combinatorics, Springer, Verlag, 25.
Sciriha, I., (2007).A characterization of singular
graphs. In: Electronic Journal of Linear Algebra, 16, 451-462.
Sciriha, I., (1998).On the construction of graphs of
nullity one. In: Discrete Mathematics, 181,193-211.
Sharaf, K. R., & Ali, D. A. (2013).Nullity and Bounds to the Nullity of Dendrimer Graphs.
In: Al-Rafidain Journal of Computer Sciences
Mathematics, 10.4, 71-861