A q-Analogue of the Addressing Problem of Graphs by Graham and Pollak
A q-Analogue of the Addressing Problem of Graphs by Graham and Pollak
复制标题
DOI：
10.1137/110831520
复制
发表时间：
2012-04
期刊：
影响因子：
--
通讯作者：
Saori Watanabe;Kota Ishii;M. Sawa
中科院分区：
文献类型：
--
作者：
Saori Watanabe;Kota Ishii;M. Sawa
在本文中，我们考虑了最初由Graham和Pollak提出的图的经典二进制寻址问题的q-ary扩展[Bell System Tech. J., 50 (1971), pp. 2495-2519]。用距离矩阵的特征值给出了寻址最小长度的下界。对于完全图和r超树，界是很明显的，但对于Petersen图则不然。作为Graham， Pollak和Sivasubramanian[线性代数应用]的美丽定理的推广，明确计算了r-超树距离矩阵的行列式。[j] .中文信息学报，431 (2009),pp. 1234-1248]。将q元寻址应用于完全图的分解。我们给出了Liu-Schwenk定理的另一种证明。号码。关于完全图分解为边不相交的完全多部图的问题。
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.