Paths and animals in unbounded degree graphs with repulsion
arXiv:1211.4212
Abstract
A class of countable infinite graphs with unbounded vertex degree is considered. In these graphs, the vertices of large degree `repel' each other, which means that the path distance between two such vertices cannot be smaller than a certain function of their degrees. Assuming that this function increases sufficiently fast, we prove that the number of finite connected subgraphs (animals) of order N containing a given vertex x is exponentially bounded in N for N belonging to an infinite subset N_x of natural numbers. Under a less restrictive condition, the same result is obtained for the number of simple paths originated at a given vertex. These results are then applied to a number of problems, including estimating the growth of the Randić index and of the number of greedy animals.