Classifying graphs by degrees

Abstract

We define seven types of vertices in a graph by considering the relationships between the degree of a vertex and the degrees of its neighbors. This leads to a natural classification of a graph according to which of the seven types of vertices it contains. Among other things, we show that only 71 of the ostensible 128 graph classes contain connected graphs, 46 of which can be realized by trees.