No Detail Found!

An asymptotic relation between the wirelength of an embedding and the Wiener index

Author(s)
K. Jagadeesh Kumar Department of Mathematics, Hindustan Institute of Technology and Science,Chennai 603103,India
Sandi Klavzar Faculty of Mathematics and Physics, University of Ljubljana, Ljubljana, Slovenia; Faculty of Natural Sciences and Mathematics, University of Maribor, Maribor, Slovenia; Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia
R. Sundara Rajan Department of Mathematics, Hindustan Institute of Technology and Science,Chennai 603103,India
Indra Rajasingh School of Advanced Sciences, Vellore Institute of Technology,Chennai 600127,India
T. M. Rajalaxmi Department of Mathematics, Sri Sivasubramaniya Nadar College of Engineering,Chennai 603110,India
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 2p-partite graphs into Cartesian products of paths and/or cycles as the function of the Wiener index is also determined. The latter result is an asymptotic approximation of the general upper bound.
Publication Details
Page(s) 74-78
Published Journal: Discrete Mathematics Letters, Volume: 7, Issue: 0, Year: 2021

Request the full text from PASTIC

Keywords
Cartesian product of graphs, embedding, integer labeling, wirelength, complete 2p-partite graph, Wiener index
References
Annexstein F. .1994 .Embedding hypercubes and related networks into mesh connected processor arrays. J. Parallel Distrib. Comput, 23 : 72-79.
Bezrukov S. L.,Chavez J. D.,Harper L. H.,Brim J.,Gruska J. .1998 .Embedding of hypercubes into grids. MFCS 1998, Lecture Notes in Computer Science, 1450 : 693-701.
Bezrukov S. L. .1998 .The cyclic wirelength of trees. Discrete Appl. Math, 87 : 275-277.
Casablanca R. M. .2014 .Average distance in the strong product of graphs, Util. , 94 : 31-48.
Chen L.,Tzeng N. F. .1994 .Structural and tree embedding aspects of incomplete hypercubes. IEEE Trans. Comput, 43 : 1434-1439.
Choudum S. A.,Sunitha V. .2002 .. Networks, 40 : 71-84.
Dobrynin A. A.,Entringer R.,I. Gutman R. .2001 .Wiener index of trees: theory and application. Acta Appl. Math, 66 : 211-249.
Dobrynin A. A.,P. A. A. .2002 .Zˇ igert, Wiener index of hexagonal systems. Acta Appl. Math, 72 : 247-294.
Eliasi M.,Raeisi G.,Taeri B. .2012 .Wiener index of some graph operations. Discrete Appl. Math, 160 : 1333-1344.
Goubko M. .2016 .Minimizing Wiener index for vertex-weighted trees with given weight and degree sequences. MATCH Commun. Math. Comput. Chem, 75 : 3-27.
Graovac A. .1991 .On the Wiener index of a graph. J. Math. Chem, 8 : 53-62.
Guu C. J. .1997 .The Circular Wirelength Problem for Hypercubes. Ph.D. dissertation, : .
Hammack R.,Imrich W.,S. Klavzˇar W. .2011 .. , : .
Ilic A. .2014 .´, A note on 'A new approach to compute Wiener index'. J. Comput. Theor. Nanosci, 11 : 958-960.
Klavzˇar S.,Rajapakse A.,I. Gutman A. .1996 .The Szeged and the Wiener index of graphs. , 9 : 45-49.
Knor M.,R. M. .2016 .Sˇ krekovski, A. Tepeh, Mathematical aspects on Wiener index. Ars Math. Contemp, 11 : 327-352.
Kuo C. N. .2017 .Cycles embedding in folded hypercubes with conditionally faulty vertices. Discrete Appl. Math, 220 : 55-59.
Manuel P.,Rajasingh I.,Rajan B.,Mercy H. .2009 .Exact wirelength of hypercube on a grid, Discrete Appl. , 157 : 1486-1495.
Manuel P.,Rajasingh I.,Rajan B.,Rajan R. S. .2013 .A new approach to compute Wiener index. J. Comput. Theor. Nanosci, 10 : 1515-1521.
Mukwembi S. .2014 .Average distance, independence number and spanning trees. J. Graph Theory, 76 : 194-199.
Nandini G. K.,Rajan R. S.,Rajalaxmi T. M.,Shantrinal A. A.,Husain S. K. S.,Hasni R. . .Wiener index via wirelength of an embedding. Discrete Math. Algorithms Appl, : .
Polansky O. E.,Bonchev D. .1986 .General theory and changes due to some graph operations. MATCH Commun. Math. Comput. Chem, 21 : 133-186.
Rajasingh I.,Arockiaraj M.,Rajan B.,Manuel P. .2012 .Minimum wirelength of hypercubes into n-dimensional grid networks. Inform. Process. Lett, 112 : 583-586.
I. Rajasingh ,Rajan R. S. .2017 .Exact wirelength of embedding circulant networks into necklace and windmill Graphs, Ars Combin. , 130 : 215-237.
Rajan R. S.,Kalinowski T.,Rajalaxmi T. M. .2021 .Lower bounds for dilation, wirelength, and edge congestion of embedding graphs into hypercubes. J. Supercomputing, 77 : 4135-4150.
Rajan R. S.,Rajalaxmi T. M.,Liu J. B. .2020 .Wirelength of embedding complete multipartite graphs into certain graphs. Discrete Appl. Math, 280 : 221-236.
Rajan R. S.,Shantrinal A. A.,Rajalaxmi T. M.,Fan J. . .Embedding complete multi-partite graphs into Cartesian product of paths and cycles. Electron. J. Graph Theory Appl., : .
Wiener H. .1947 .Structural determination of paraffin boiling points. J. Am. Chem. Soc, 69 : 17-20.
J. M. Xu .2001 .. Topological Structure and Analysis of Interconnection Networks, : .
Yeh Y.-N.,I. Gutman Y.-N. .1994 .On the sum of all distances in composite graphs. , 135 : 359-365.
Zhang Z.,Huang S.-Q.,Guo D.,Li Y.-H.,RVCCC: Y.-H. .2019 .a new variational network of cube-connected cycles and its topological properties. Theoret. Comput. Sci, 767 : 34-50.
0

Citations

0

Downloads

12

Views