Addressing Johnson Graphs, Complete Multipartite Graphs, Odd Cycles, and Random Graphs

Noga Alon, Sebastian M. Cioabă, Brandon D. Gilbert, Jack H. Koolen, Brendan D. McKay

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


Graham and Pollak showed that the vertices of any graph G can be addressed with N-tuples of three symbols, such that the distance between any two vertices may be easily determined from their addresses. An addressing is optimal if its length N is minimum possible. In this article, we determine an addressing of length (Formula presented.) for the Johnson graphs J(n, k) and we show that our addressing is optimal when k = 1 or when (Formula presented.), but not when n = 6 and k = 3. We study the addressing problem as well as a variation of it in which the alphabet used has more than three symbols, for other graphs such as complete multipartite graphs and odd cycles. We also present computations describing the distribution of the minimum length of addressings for connected graphs with up to 10 vertices. Motivated by these computations we settle a problem of Graham, showing that most graphs on n vertices have an addressing of length at most (Formula presented.).

Original languageEnglish (US)
Pages (from-to)372-382
Number of pages11
JournalExperimental Mathematics
Issue number3
StatePublished - 2021

All Science Journal Classification (ASJC) codes

  • General Mathematics


  • Johnson graphs
  • addressing
  • biclique partition
  • eigenvalue
  • random graphs


Dive into the research topics of 'Addressing Johnson Graphs, Complete Multipartite Graphs, Odd Cycles, and Random Graphs'. Together they form a unique fingerprint.

Cite this