Grant Molnar, Brigham Young University
Mathematical Sciences
One important attribute of a network of points, or graph, is its independence number: the maximum size of a set of points (vertices) in which no two vertices are joined by an edge. The degree sequence of a graph is a list recording the number of edges that meet at each vertex. The residue of a graph is a number computed by an algorithm that reduces the degree sequence to a string of zeroes. Calculating the independence number of large graphs in general is believed to be computationally hard. However, the residue can be calculated much more easily and is a lower bound for the independence number. In many cases res(G)=ind(G), and it is an open question when equality holds.
Our research focuses on when res(G)≠ind(G). We study this by analyzing the minimal graphs with residues differing from their independence numbers, and by considering how a degree sequence can be modified without changing its residue. We present results regarding these graphs and degree sequences that lead to many conditions under which the residue of a graph equals its independence number. We generate all minimal graphs of order less than 9 for which res(G)≠ind(G) and discuss the form of larger minimal graphs. We also discuss certain cases in which res(G)=ind(G) in spite of having one of these minimal graphs as a subgraph. We showcase a variety of transformations that can be applied to a degree sequence without changing its residue, and examine the implications of these transformations for the construction of larger minimal graphs. Our findings offer insight into the open question of when the residue of a graph is equal to its independence number, and this improves our understanding of when the independence number can be efficiently computed.