Distance Sequences In Locally Infinite Vertex-Transitive Digraphs |
| |
Authors: | Wesley Pegden |
| |
Institution: | (1) Department of Mathematics, Rutgers University, Piscataway, NJ, 08854-8019, USA |
| |
Abstract: | We prove that the out-distance sequence {f+(k)} of a vertex-transitive digraph of finite or infinite degree satisfies f+(k+1)≤f+(k)2 for k≥1, where f+(k) denotes the number of vertices at directed distance k from a given vertex. As a corollary, we prove that for a connected vertex-transitive undirected graph of infinite degree
d, we have f(k)=d for all k, 1≤k<diam(G). This answers a question by L. Babai. |
| |
Keywords: | 05C12 |
本文献已被 SpringerLink 等数据库收录! |
|