Graphs with a given conditional diameter that maximize the Wiener index

Junfeng An; Yingzhi Tian; Junfeng An; Yingzhi Tian

doi:10.3934/math.2024770

AIMS Mathematics

2024, Volume 9, Issue 6: 15928-15936. doi: 10.3934/math.2024770

Previous Article Next Article

Research article

Graphs with a given conditional diameter that maximize the Wiener index

Junfeng An ,
Yingzhi Tian ^,

College of Mathematics and System Sciences, Xinjiang University, Urumqi, Xinjiang 830046, China

Received: 01 March 2024 Revised: 01 April 2024 Accepted: 15 April 2024 Published: 06 May 2024
MSC : 05C09

The Wiener index $ W(G) $ of a graph $ G $ is one of the most well-known topological indices, which is defined as the sum of distances between all pairs of vertices of $ G $. The diameter $ D(G) $ of $ G $ is the maximum distance between all pairs of vertices of $ G $, and the conditional diameter $ D(G; s) $ is the maximum distance between all pairs of vertex subsets with cardinality $ s $ of $ G $. When $ s = 1 $, the conditional diameter $ D(G; s) $ is just the diameter $ D(G) $. The authors in ^[18] characterized the graphs with the maximum Wiener index among all graphs with diameter $ D(G) = n-c $, where $ 1\le c\le 4 $. In this paper, we will characterize the graphs with the maximum Wiener index among all graphs with conditional diameter $ D(G; s) = n-2s-c $ ($ -1\leq c\leq 1 $), which extends partial results above.
- Wiener index,
- diameter,
- conditional diameter
Citation: Junfeng An, Yingzhi Tian. Graphs with a given conditional diameter that maximize the Wiener index[J]. AIMS Mathematics, 2024, 9(6): 15928-15936. doi: 10.3934/math.2024770

Related Papers:

Abstract

The Wiener index $ W(G) $ of a graph $ G $ is one of the most well-known topological indices, which is defined as the sum of distances between all pairs of vertices of $ G $. The diameter $ D(G) $ of $ G $ is the maximum distance between all pairs of vertices of $ G $, and the conditional diameter $ D(G; s) $ is the maximum distance between all pairs of vertex subsets with cardinality $ s $ of $ G $. When $ s = 1 $, the conditional diameter $ D(G; s) $ is just the diameter $ D(G) $. The authors in ^[18] characterized the graphs with the maximum Wiener index among all graphs with diameter $ D(G) = n-c $, where $ 1\le c\le 4 $. In this paper, we will characterize the graphs with the maximum Wiener index among all graphs with conditional diameter $ D(G; s) = n-2s-c $ ($ -1\leq c\leq 1 $), which extends partial results above.

References

[1]	M. L. Bai, Y. Z. Tian, Wiener index of the direct product of a path and a generalized petersen graph, J. Xinjiang Univ., 41 (2024), 218–227. https://doi.org/10.13568/j.cnki.651094.651316.2023.04.13.0002 doi: 10.13568/j.cnki.651094.651316.2023.04.13.0002
[2]	J. A. Bondy, U. S. R. Murty, Graph theory, Berlin: Springer, 2008. https://doi.org/10.1007/978-1-84628-970-5
[3]	Q. Cai, T. Li, Y. Shi, H. Wang, Sum of weighted distances in trees, Discrete Appl. Math., 257 (2019), 67–84. https://doi.org/10.1016/j.dam.2018.08.033 doi: 10.1016/j.dam.2018.08.033
[4]	S. Cambie, An asymptotic resolution of a problem of Plesník, J. Comb. Theory. Ser. B, 145 (2020), 341–358. https://doi.org/10.1016/j.jctb.2020.06.003 doi: 10.1016/j.jctb.2020.06.003
[5]	S. Cambie, Extremal total distance of graphs of given radius I, J. Graph Theory, 97 (2021), 104–122. https://doi.org/10.1002/jgt.22644 doi: 10.1002/jgt.22644
[6]	S. Cambie, Corrigendum on Wiener index, Zagreb Indices and Harary index of Eulerian graphs, Discrete Appl. Math., 347 (2024), 139–142. https://doi.org/10.1016/j.dam.2024.01.011 doi: 10.1016/j.dam.2024.01.011
[7]	K. C. Das, M. J. Nadjafi-Arani, On maximum Wiener index of trees and graphs with given radius, J. Comb. Optim., 34 (2017), 574–587. https://doi.org/10.1007/s10878-016-0092-y doi: 10.1007/s10878-016-0092-y
[8]	E. DeLaViña, B. Waller, Spanning trees with many leaves and average distances, Electron. J. Comb., 15 (2008). https://doi.org/10.37236/757 doi: 10.37236/757
[9]	A. A. Dobrynin, R. Entringer, I. Gutman, Wiener index of trees: Theory and applications, Acta Appl. Math., 66 (2001), 211–249. https://doi.org/10.1023/a:1010767517079 doi: 10.1023/a:1010767517079
[10]	Y. L. Jin, X. D. Zhang, On the two conjectures of the Wiener index, arXiv, 2013. https://doi.org/10.48550/arXiv.1304.0873 doi: 10.48550/arXiv.1304.0873
[11]	M. Knor, R. Škrekovski, A. Tepeh, Mathematical aspects of Wiener index, arXiv, 2015, 1–28. https://doi.org/10.48550/arXiv.1510.00800 doi: 10.48550/arXiv.1510.00800
[12]	M. Knor, R. Škrekovski, A. Tepeh, Selected topics on Wiener index, arXiv, 2023, 1–34. https://doi.org/10.48550/arXiv.2303.11405 doi: 10.48550/arXiv.2303.11405
[13]	H. Liu, X. Pan, On the Wiener index of trees with fixed diameter, MATCH Commun. Math. Comput. Chem., 60 (2008), 85–94.
[14]	S. Mukwembi, T. Vertík, Wiener index of trees of given order and diameter at most 6, Bull. Aust. Math. Soc., 89 (2014), 379–396. https://doi.org/10.1017/S0004972713000816 doi: 10.1017/S0004972713000816
[15]	J. Plesník, On the sum of all distances in a graph or digraph, J. Graph Theory, 8 (1984), 1–21. https://doi.org/10.1002/jgt.3190080102 doi: 10.1002/jgt.3190080102
[16]	A. V. Sills, H. Wang, On the maximal Wiener index and related questions, Discrete Appl. Math., 160 (2012), 1615–1623. https://doi.org/10.1016/j.dam.2012.03.002 doi: 10.1016/j.dam.2012.03.002
[17]	D. Stevanović, Maximizing Wiener index of graphs with fixed maximum degree, MATCH Commun. Math. Comput. Chem., 60 (2008), 71–83.
[18]	Q. Sun, B. Ikica, R. Škrekovski, V. Vukašinović, Graphs with a given diameter that maximise the Wiener index, Appl. Math. Comput., 356 (2019), 438–448. https://doi.org/10.1016/j.amc.2019.03.025 doi: 10.1016/j.amc.2019.03.025
[19]	S. Wang, X. Guo, Trees with extremal Wiener indices, MATCH Commun. Math. Comput. Chem., 60 (2008), 609–622.
[20]	H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc., 69 (1947), 17–20. https://doi.org/10.1021/ja01193a005 doi: 10.1021/ja01193a005
[21]	K. Xu, M. Liu, K. C. Das, I. Gutman, B. Furtula, A survey on graphs extremal with respect to distance-based topological indices, MATCH Commun. Math. Comput. Chem., 2014. https://scidar.kg.ac.rs/handle/123456789/17378
[22]	X. D. Zhang, Y. Liu, M. X. Han, Maximum Wiener index of trees with given degree sequence, arXiv, 2009, 1–19. https://doi.org/10.48550/arXiv.0907.3772 doi: 10.48550/arXiv.0907.3772

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)