20.500.12556/DKUM-90784 An asymptotic relation between the wirelength of an embedding and the Wiener index Asimptotična relacija med žično dolžino vložitve in Wienerjevim indeksom 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. Žična dolžina žice je pomembno merilo za oceno kakovosti vložitve grafa v gostiteljski graf in se uporablja zlasti v VLSI načrtih. Wienerjev indeks igra pomembno vlogo v matematični kemiji, kemoinformatiki in drugje. V tej članku povežemo ta dva koncepta tako, da dokažemo, da je Wienerjev indeks gostiteljskega grafa zgornja meja žične dolžine dane vložitve. Kot funkcija Wienerjevega indeksa je določena žična dolžina vložitve polnih ▫$2^p$▫-partitnih grafov v kartezični produkt poti in/ali ciklov. Rezultat je asimptotična aproksimacija splošne zgornje meje. Wiener index embedding wirelength complete 2p-partite graph Cartesian product of graphs integer labeling Wienerjev index vložitev žična dolžina polni 2p-partitni graf kartezični produkt grafov celoštevilska označitev true false true National University of Computer and Emerging Science, University of Management and Technology, University of Management and Technology Angleški jezik Slovenski jezik Znanstveno delo 2024-09-23 11:18:41 2024-09-23 11:46:07 2024-09-24 03:09:22 0000-00-00 00:00:00 2021 0 0 Str. 74-78 Letn. 7 2021 0000-00-00 Zaloznikova Objavljeno NiDoloceno 2021-06-14 2021-07-16 2021-07-17 519.17 70732035 10.47443/dml.2021.0063 2664-2557 Kumar-2021-An_asymptotic_relation_between_the.pdf Kumar-2021-An_asymptotic_relation_between_the.pdf 1 621202A9CD656BBD2D699C107E0C85D6 9b9a09210461ba157da8f2c9faaef0aafc64ec4147234b64ef24d25d22a5e060 8ec002dd-798f-11ef-8363-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=185710 https://www.dmlett.com/journal-archive/v7/ 0 c4a9fbbd-798f-11ef-8363-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=185711 Fakulteta za naravoslovje in matematiko 0 0 0