×

Average distance is submultiplicative and subadditive with respect to the strong product of graphs. (English) Zbl 1426.05146

Summary: We show that the average distance is submultiplicative and subadditive on the set of non-trivial connected graphs with respect to the strong product. We also give an application of the above-mentioned result.

MSC:

05C76 Graph operations (line graphs, products, etc.)
05C12 Distance in graphs

Software:

KronFit
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] An, X.; Wu, B., The Wiener index of the \(k\) th power of a graph, Appl. Math. Lett., 21, 5, 436-440 (2008) · Zbl 1138.05321
[2] Bollobás, B.; Kozma, R.; Miklós, D., Handbook of large-scale random networks, (Bolyai Society Mathematical Studies, vol. 18 (2009), János Bolyai Mathematical Society, Budapest: János Bolyai Mathematical Society, Budapest Springer, Berlin), 538 · Zbl 1170.05053
[3] Brandes, U.; Erlebach, T., Network Analysis: Methodological Foundations (Lecture Notes in Computer Science) (2005), Springer-Verlag New York, Inc.: Springer-Verlag New York, Inc. Secaucus, NJ, USA · Zbl 1069.68001
[4] Chung, F. R.K., The average distance and the independence number, J. Gr. Theory, 12, 2, 229-235 (1988) · Zbl 0644.05029
[5] Dobrynin, A. A., Wiener index of hexagonal chains with segments of equal length, Quantitative Graph Theory, 81-109 (2015), CRC Press: CRC Press Boca Raton, FL
[6] Doyle, J. K.; Graver, J. E., Mean distance in a graph, Discr. Math., 7, 2, 147-154 (1977) · Zbl 0361.05045
[7] Eliasi, M.; Raeisi, G.; Taeri, B., Wiener index of some graph operations, Discr. Appl. Math., 160, 9, 1333-1344 (2012) · Zbl 1239.05051
[8] Entringer, R. C.; Jackson, D. E.; Snyder, D. A., Distance in graphs, Czechoslov. Math. J., 26(101), 2, 283-296 (1976) · Zbl 0329.05112
[9] Graham, R. L.; Knuth, D. E.; Patashnik, O., Concrete Mathematics: A Foundation for Computer Science (1994), Addison-Wesley Publishing Company: Addison-Wesley Publishing Company Reading, MA · Zbl 0836.00001
[10] Graovac, A.; Pisanski, T., On the Wiener index of a graph, J. Math. Chem., 8, 1-3, 53-62 (1991)
[11] Gutman, I.; Cruz, R.; Rada, J., Wiener index of Eulerian graphs, Discr. Appl. Math., 162, 247-250 (2014) · Zbl 1298.05093
[12] Hammack, R.; Imrich, W.; Klavžar, S., Handbook of product graphs, Discrete Mathematics and its Applications (2011), CRC Press: CRC Press Boca Raton, FL · Zbl 1283.05001
[13] Hsu, L.-H.; Lin, C.-K., Graph Theory and Interconnection Networks (2009), CRC Press: CRC Press Boca Raton, FL · Zbl 1168.05002
[14] Hu, M., Wiener index of a type of composite graph, Ars Combin., 106, 59-64 (2012) · Zbl 1289.05122
[16] Knor, M.; Potočnik, P.; Škrekovski, R., The Wiener index in iterated line graphs, Discr. Appl. Math., 160, 15, 2234-2245 (2012) · Zbl 1251.05047
[17] Knor, M.; Škrekovski, R., Wiener index of line graphs, Quantitative Graph theory, 279-301 (2015), CRC Press: CRC Press Boca Raton, FL
[18] (Kranakis, E., Advances in network analysis and its applications, Mathematics in Industry, vol. 18 (2013), Springer: Springer Heidelberg) · Zbl 1254.00030
[19] Lei, H.; Li, T.; Shi, Y.; Wang, H., Wiener polarity index and its generalization in trees, MATCH Commun. Math. Comput. Chem., 78, 1, 199-212 (2017) · Zbl 1471.92446
[20] Leskovec, J.; Chakrabarti, D.; Kleinberg, J.; Faloutsos, C.; Ghahramani, Z., Kronecker graphs: an approach to modeling networks, J. Mach. Learn. Res., 11, 985-1042 (2010) · Zbl 1242.05256
[21] Luo, Y.; Wang, L. G., Wiener indices of a class of graphs and their line graphs, J. Nat. Sci. Hunan Norm. Univ., 37, 1, 81-85 (2014) · Zbl 1313.05096
[22] Ma, J.; Shi, Y.; Wang, Z.; Yue, J., On Wiener polarity index of bicyclic networks, Sci. Rep., 6, 19066 (2016)
[23] Malarz, K.; Czaplicki, J.; Kawecka-Magiera, B.; Kułakowski, K., Average distance in growing trees, Int. J. Mod. Phys. C, 14, 09, 1201-1206 (2003)
[24] Milgram, S., The small world problem, Psychol. Today, 2, 1, 60-67 (1967)
[25] Newman, M. E.J., Networks: An Introduction (2010), Oxford University Press: Oxford University Press Oxford · Zbl 1195.94003
[26] Parsonage, E.; Nguyen, H.; Bowden, R.; Knight, S.; Falkner, N.; Roughan, M., Generalized graph products for network design and analysis, Proceedings of the Ninteenth IEEE International Conference on Network Protocols, 79-88 (2011)
[27] Pattabiraman, K., Exact Wiener indices of the strong product of graphs, J. Prime Res. Math., 9, 18-33 (2013) · Zbl 1301.05110
[28] Pattabiraman, K.; Paulraja, P., Wiener and vertex PI indices of the strong product of graphs, Discuss. Math. Graph Theory, 32, 4, 749-769 (2012) · Zbl 1291.05050
[29] Peterin, I.; Pleteršek, P., Wiener index of strong product of graphs, Opuscula Math., 38, 1 (2018), , to appear · Zbl 1402.05056
[30] Roy, K.; Kar, S.; Das, R., Understanding the Basics of QSAR for Applications in Pharmaceutical Sciences and Risk Assessment (2015), Elsevier London, Inc.
[31] Senbagamalar, J.; Babujee, J. B.; Gutman, I., On Wiener index of graph complements, Trans. Comb., 3, 2, 11-15 (2014) · Zbl 1463.05109
[32] Todeschini, R.; Consonni, V., Handbook of Molecular Descriptors (2000), Wiley-VCH Verlag: Wiley-VCH Verlag Weinheim
[33] Weichsel, P. M., The Kronecker product of graphs, Proc. Amer. Math. Soc., 13, 47-52 (1962) · Zbl 0102.38801
[34] Wiener, H. J., Structural determination of paraffin boiling points, J. Am. Chem. Soc., 69, 17-20 (1947)
[35] Ye, Q.; Wu, B.; Wang, B., Distance distribution and average shortest path length estimation in real-world networks, (Cao, L.; Feng, Y.; Zhong, J., Advanced Data Mining and Applications. Advanced Data Mining and Applications, Lecture Notes in Computer Science, vol. 6440 (2010), Springer: Springer Berlin Heidelberg), 322-333
[36] Yeh, Y. N.; Gutman, I., On the sum of all distances in composite graphs, Discr. Math., 135, 1-3, 359-365 (1994) · Zbl 0814.05033
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.