A q -Analogue of the Addressing Problem of Graphs by Graham and Pollak
Watanabe Saori, Kota Ishii, Masanori Sawa · SIAM Journal on Discrete Mathematics · 2012
In this paper we consider a q-ary extension of the classical binary addressing problem of graphs which was originally posed by Graham and Pollak [Bell System Tech. J., 50 (1971), pp. 2495–2519]. A lower bound for the minimum length of addressings is presented in terms of eigenvalues of distance matrices. The bound is sharp for complete graphs and r-hypertrees but not for the Petersen graph. The determinant of the distance matrices of r-hypertrees is explicitly calculated, as a generalization of beautiful theorems by Graham and Pollak and Sivasubramanian [Linear Algegra Appl., 431 (2009), pp. 1234–1248] on trees and 3-hypertrees. The q-ary addressings are applied to the decomposition of the complete graphs. We give an alternative proof of the Liu–Schwenk theorem [Congr. Numer., 81 (1991), pp. 129–142] on the decomposition of the complete graphs into edge-disjoint complete multipartite graphs.