Approximately uniformly locally finite graphs

Let Gamma be a locally finite graph, L the normalized Laplacian of Gamma. If Gamma is uniformly locally finite, i.e. if each vertex has no more than d adjacent vertices, then the matrix of L (with respect to the standard basis) has no more than d + 1 non-zero entries in each row and in each column. We consider the class of locally finite graphs, for which the Laplacian can be approximated, with respect to the operator norm, by matrices of this type with arbitrary d. We provide examples of locally finite graphs which are or are not in this class, and show that the graphs from this class share certain regularity property: vertices of high degree cannot have too many adjacent vertices of low degree. (C) 2019 Elsevier Inc. All rights reserved.