Gathering Information about a Graph by Counting Walks from a Single Vertex
<|reference_start|>Gathering Information about a Graph by Counting Walks from a Single Vertex: We say that a vertex $v$ in a connected graph $G$ is decisive if the numbers of walks from $v$ of each length determine the graph $G$ rooted at $v$ up to isomorphism among all connected rooted graphs with the same number of vertices. On the other hand, $v$ is called ambivalent if it has the same walk counts as a vertex in a non-isomorphic connected graph with the same number of vertices as $G$. Using the classical constructions of cospectral trees, we first observe that ambivalent vertices exist in almost all trees. If a graph $G$ is determined by spectrum and its characteristic polynomial is irreducible, then we prove that all vertices of $G$ are decisive. Note that both assumptions are conjectured to be true for almost all graphs. Without using any assumption, we are able to prove that the vertices of a random graph are with high probability distinguishable from each other by the numbers of closed walks of length at most 4. As a consequence, the closed walk counts for lengths 2, 3, and 4 provide a canonical labeling of a random graph. Answering a question posed in chemical graph theory, we finally show that all walk counts for a vertex in an $n$-vertex graph are determined by the counts for the $2n$ shortest lengths, and the bound $2n$ is here asymptotically tight.<|reference_end|>
@article{fuhlbrück2024gathering,
    title={Gathering Information about a Graph by Counting Walks from a Single
  Vertex},
    author={Frank Fuhlbr"uck, Johannes K"obler, Oleg Verbitsky, and Maksim
  Zhukovskii},
    journal={arXiv preprint arXiv:2409.03690},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.03690},
    primaryClass={cs.DM math.CO}
}