Reliability Hosoya-Wiener Polynomial of Double Weighted Trees

• Autorzy: Rupnik Poklukar D. , Žerovnik J.

Identyfikatory

DOI

10.3233/FI-2016-1416

• Języki publikacji: EN

Abstrakty

EN

Reliability Hosoya-Wiener polynomial for edge weighted graphs is defined, that can be used as a measure of reliability of a communication network. Each edge is assigned two weights, reliability and communication delay. Some basic properties are given and a recursive formula for the reliability Hosoya-Wiener polynomial of a rooted tree is proved that yields a linear time algorithm on weighted trees. On general graphs, the reliability Hosoya-Wiener polynomial can be computed in O(n³) time.

Słowa kluczowe

EN

communication network; reliability Hosoya-Wiener polynomial

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 147, nr 4
• Strony: 447--456
• Opis fizyczny: Bibliogr. 20 poz., rys.

Twórcy

autor

Rupnik Poklukar D.

• FME, University of Ljubljana, Aškerčeva 6, Ljubljana 1000, Slovenia

autor

Žerovnik J.

• FME, University of Ljubljana, Aškerčeva 6, Ljubljana 1000, Slovenia

Bibliografia

• [1] Banič I, Erveš R, Žerovnik J. Edge, vertex and mixed fault diameters, Advances in Applied Mathematics, 2009;43(3):231-238. doi:10.1016/j.aam.2009.01.005.
• [2] Bermond JC, Bond J, Paoli M, Peyrat C. Graphs and interconnection networks: diameter and vulnerability. In Surveys in combinatorics (Southampton, 1983), volume 82 of London Math. Soc. Lecture Note Ser., pages 1–30. Cambridge Univ. Press, Cambridge, 1983. Available from: http://dx.doi.org/10.1017/CBO9781107325548.
• [3] Denejko P, Diks K, Pelc A, Piotrow M. Reliable Minimum Finding Comparator Networks, Fundamenta Informaticae 2000;42(3-4): 235-249. Available from: http://dl.acm.org/citation.cfm?id=354609.354612.
• [4] Elenbogen BS, Fink JF. Distance distributions for graphs modeling computer networks, Discrete Applied Mathematics, 2007;155(18):2612-2624. doi:10.1016/j.dam.2007.07.020.
• [5] Erveš R, Rupnik Poklukar D, Žerovnik J. On vulnerability measures of networks, Croatian Operational Research Review, 2013;4:318-333.
• [6] Erveš R, Žerovnik J. Wide-diameter of Product Graphs, Fundamenta Informaticae, 2013;125:153-160. doi:10.3233/FI-2013-857.
• [7] Gutman I, Furtula B (eds.) Distance in Molecular Graphs - Theory, Univ. Kragujevac, Kragujevac, 2012. ISBN:978-86-6009-012-8.
• [8] Holmgren AJ. Using Graph Models to analyze the Vulnerability of Electric Power Networks, Risk analysis, 2006;26:955-969. doi:10.1111/j.1539-6924.2006.00791.x.
• [9] Hosoya H. On some counting polynomials in chemistry, Discrete Appl. Math., 1988;19(1-3):239-257. doi:10.1016/0166-218X(88)90017-0.
• [10] Krishnamoorthy M, Krishnamurty B. Fault diameter of interconnection networks, Comput. Math. Appl., 1987;13(5-6):577-582. Available from: http://dl.acm.org/citation.cfm?id=35064.36256.
• [11] Z. N. Odabaş ZN, Aytaç A. Residual Closeness in Cycles and Related Networks, Fundamenta Informaticae, 2013;124(3):297-307. doi:10.3233/FI-2013-835.
• [12] Rodríguez-Velázquez JA, Kamišalić A, Domingo-Ferrer J. On reliability indices of communication networks, Comput. Math. Appl., 2009;58(7):1433-1440. doi:10.1016/j.camwa.2009.07.019.
• [13] Rupnik Poklukar D, Žerovnik J. On the reliability Wiener number, Iranian Journal of Mathematical Chemistry, 2014;5:107–118. Available from: http://ijmc.kashanu.ac.ir/article_7377.html.
• [14] Rupnik Poklukar D, Žerovnik J. The reliability Wiener number of cartesian product graphs, Iranian Journal of Mathematical Chemistry, 2015;6(2):129–135. Available from: http://ijmc.kashanu.ac.ir/article_10428.html.
• [15] Sagan BE, Yeh YN, Zhang P. TheWiener Polynomial of a Graph, Int. J. Quantum Chem., 1996;60(5):959-969. doi:10.1002/(SICI)1097-461X(1996)60:5¡959::AID-QUA2¿3.0.CO;2-W.
• [16] Vardi Y, Zhang CH. Measures of Network Vulnerability, Signal Processing Letters, 2007;14(5):313-316. doi:10.1109/LSP.2006.888290.
• [17] Wiener H. Structural determination of paraffin boiling points, J. Amer. Chem. Soc., 1947;69:17-20.
• [18] Yin JH, Li JS, Chen GL, Zhong C. On the Fault-tolerant diameter and wide diameter of ω-connected graphs, Networks, 2005;45:88-94.
• [19] Zmazek B, Žerovnik J. Computing the weighted Wiener and Szeged number on weighted cactus graphs in linear time, Croat. Chem. Acta, 2003;76(2):137-143. Available from: http://hrcak.srce.hr/103089.
• [20] Zmazek B, Žerovnik J. On generalization of the Hosoya-Wiener polynomial, MATCH Commun. Math. Comput. Chem., 2006;55:359–362. Available from: http://www.worldcat.org/oclc/441080730.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).