Addressing Graph Products and Distance-Regular Graphs
| Autor: | Sebastian M. Cioabă, Michelle Markiewitz, Trevor Vanderwoerd, Kevin N. Vander Meulen, Randall J. Elzinga |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
FOS: Computer and information sciences
Discrete Mathematics (cs.DM) Applied Mathematics 010102 general mathematics 0102 computer and information sciences 01 natural sciences Upper and lower bounds Graph Combinatorics Hamming graph Distance matrix 010201 computation theory & mathematics FOS: Mathematics Discrete Mathematics and Combinatorics Mathematics - Combinatorics Combinatorics (math.CO) 0101 mathematics Tuple Connectivity Mathematics Computer Science - Discrete Mathematics MathematicsofComputing_DISCRETEMATHEMATICS |
| DOI: | 10.48550/arxiv.1609.05995 |
| Popis: | Graham and Pollak showed that the vertices of any connected graph $G$ can be assigned $t$-tuples with entries in $\{0, a, b\}$, called addresses, such that the distance in $G$ between any two vertices equals the number of positions in their addresses where one of the addresses equals $a$ and the other equals $b$. In this paper, we are interested in determining the minimum value of such $t$ for various families of graphs. We develop two ways to obtain this value for the Hamming graphs and present a lower bound for the triangular graphs. Comment: 10 pages, 2 figures; This version is identical to the first in content, but it includes more explicit attributions to David A. Gregory. In particular, for Lemmas 3.1, 3.2, Remark 3.4 and Theorem 3.5 and includes an added acknowledgement |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|