Abstract: Wirelength is an important criterion to validate the quality of an embedding of a graph into a host graph and is used in particular in VLSI (Very-Large-Scale Integration) layout designs. Wiener index plays a significant role in mathematical chemistry, cheminformatics, and elsewhere. In this note these two concepts are related by proving that the Wiener index of a host graph is an upper bound for the wirelength of a given embedding. The wirelength of embedding complete ▫$2^p$▫-partite graphs into Cartesian products of paths and/or cycles as the function of the Wiener index is determined. The result is an asymptotic approximation of the general upper bound.Keywords: Wiener index, embedding, wirelength, complete 2p-partite graph, Cartesian product of graphs, integer labelingPublished in DKUM: 23.09.2024; Views: 0; Downloads: 2 Full text (365,63 KB)This document has many files! More...
