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.

An optical orthogonal signature pattern code (OOSPC) finds application in transmitting 2-D images through multicore fiber in code-division multiple-access (CDMA) communication systems. Observing a one-to-one correspondence between an OOSPC and a certain combinatorial subject, called a packing design, we present a construction of optimal OOSPCs with weight 4 and maximum collision parameter 2, which generalizes a well-known Köhler construction of optimal optical orthogonal codes (OOC) with weight 4 and maximum collision parameter 2. Using this new construction enables one to obtain infinitely many optimal OOSPCs, whose existence was previously unknown. We prove that for a multiple n of 4, there exists no optimal OOSPC of size 6 n with weight 4 and maximum collision parameter 2, together with a report which shows a gap between optimal OOCs and optimal OOSPCs when 6 and n are not coprime. We also present a recursive construction of OOSPCs which are asymptotically optimal with respect to the Johnson bound. As a by-product, we obtain an asymptotically optimal (m, n, 4, 2)-OOSPC for all positive integers m and n.