A Q-ANALOGUE OF THE ADDRESSING PROBLEM OF GRAPHS BY GRAHAM AND POLLAK

作者：Watanabe Saori^*; Ishii Kota; Sawa Masanori

来源：SIAM Journal on Discrete Mathematics, 2012, 26(2): 527-536.

DOI：10.1137/110831520

• addressing scheme
• distance matrix
• graph decomposition
• hypertree
• isometric embedding
• Liu Schwenk theorem

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.

• 出版日期2012