Change of nullity of a graph under two operations

Abstract

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.