| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 418295 | Discrete Applied Mathematics | 2014 | 9 Pages |
Two classes of infinite graphs with unbounded vertex degrees are introduced and studied. These are gg-tempered and strongly gg-tempered graphs, respectively. In such graphs, the degree growth is controlled by a function g:R+→R+g:R+→R+. It is proven that for g(t)=logtg(t)=logt (resp. g(t)=tlogtg(t)=tlogt), the number of simple paths of length NN originated at a given vertex xx (resp. the number of finite connected subgraphs of order NN containing xx) is exponentially bounded in NN for NN belonging to an infinite subset Nx⊂NNx⊂N, which is a sequence {Nk}{Nk} for gg-tempered (resp. {N:N≥Nx}{N:N≥Nx} for strongly gg-tempered) graphs. It is shown that the graphs in which the path distance between vertices of large degree is bigger than a certain function of their degrees belong to the classes introduced in this paper. These results are then applied to a number of problems, including estimating volume growth, the growth of the Randić index, and of the number of greedy animals.
