How local constraints influence network diameter and applications to LCL generalizations

In this paper, we investigate how local rules enforced at every node can influence the topology of a network. More precisely, we establish several results on the diameter of trees as a function of the number of nodes, as listed below. These results have important consequences on the landscape of locally checkable labelings (LCL) on unbounded degree graphs, a case in which our lack of knowledge is in striking contrast with that of bounded degree graphs, that has been intensively studied recently. [See paper for full abstract.]