2018/08/14 by Noga Alon, Sebastian M. Cioabă, Alon, Noga +7 · 1 citation
Computer Science · Engineering · Mathematics · #05C12 #05C35 #05C50 #05C62 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1808.04757
openalex publication_date 2018/08/14 · openalex created_date 2022/08/04 · openalex updated_date 2026/07/28
Graham and Pollak showed that the vertices of any graph G can be addressed\nwith N-tuples of three symbols, such that the distance between any two\nvertices may be easily determined from their addresses. An addressing is\noptimal if its length N is minimum possible.\n In this paper, we determine an addressing of length k(n-k) for the Johnson\ngraphs J(n,k) and we show that our addressing is optimal when k=1 or when\nk=2, n=4,5,6, but not when n=6 and k=3. We study the addressing problem\nas well as a variation of it in which the alphabet used has more than three\nsymbols, for other graphs such as complete multipartite graphs and odd cycles.\nWe also present computations describing the distribution of the minimum length\nof addressings for connected graphs with up to 10 vertices. Motivated by\nthese computations we settle a problem of Graham, showing that most graphs on\nn vertices have an addressing of length at most n-(2-o(1))\log2 n.\n