The nonregular, bipartite, integral graphs with maximum degree 4. Part I: Basic properties

Abstract

A graph is integral if the spectrum (of its adjacency matrix) consists entirely of integers. In this paper, we begin the search of those integral graphs which are nonregular, bipartite and have maximum degree 4. Here, we investigate the structure of these graphs, and provide many properties which facilitate a computer search. Among others, we have shown that any graph in question has not more than 78 vertices.