no. 4
Comparative results between the number of subtrees and Wiener index of graphs
RAIRO. Operations Research, Tome 56 (2022) no. 4, pp. 2495-2511

For a graph G, we denote by N(G) the number of non-empty subtrees of G. If G is connected, its Wiener index W(G) is the sum of distances between all unordered pairs of vertices of G. In this paper we establish some comparative results between N and W. It is shown that N(G) > W(G) if G is a graph of order n ≥ 7 and diameter 2 or 3. Also some graphs are constructed with large diameters and N > W. Moreover, for a tree T ≇ S$$ of order n, we prove that W(T) > N(T) if T is a starlike tree with maximum degree 3 or a tree with exactly two vertices of maximum degrees 3 one of which has two leaf neighbors, or a broom with klog2 n leaves. And a method is provided for constructing the graphs with N < W. Finally several related open problems are proposed to the comparison between N and W.

DOI : 10.1051/ro/2022118
Classification : 05C09, 05C30, 05C35
Keywords: Number of subtrees, Wiener index, graph with diameter 2 or 3, tree 
@article{RO_2022__56_4_2495_0,
     author = {Xu, Kexiang and Li, Jie and Luo, Zuwen},
     title = {Comparative results between the number of subtrees and {Wiener} index of graphs},
     journal = {RAIRO. Operations Research},
     pages = {2495--2511},
     year = {2022},
     publisher = {EDP-Sciences},
     volume = {56},
     number = {4},
     doi = {10.1051/ro/2022118},
     mrnumber = {4464457},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2022118/}
}
TY  - JOUR
AU  - Xu, Kexiang
AU  - Li, Jie
AU  - Luo, Zuwen
TI  - Comparative results between the number of subtrees and Wiener index of graphs
JO  - RAIRO. Operations Research
PY  - 2022
SP  - 2495
EP  - 2511
VL  - 56
IS  - 4
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2022118/
DO  - 10.1051/ro/2022118
LA  - en
ID  - RO_2022__56_4_2495_0
ER  - 
%0 Journal Article
%A Xu, Kexiang
%A Li, Jie
%A Luo, Zuwen
%T Comparative results between the number of subtrees and Wiener index of graphs
%J RAIRO. Operations Research
%D 2022
%P 2495-2511
%V 56
%N 4
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2022118/
%R 10.1051/ro/2022118
%G en
%F RO_2022__56_4_2495_0
Xu, Kexiang; Li, Jie; Luo, Zuwen. Comparative results between the number of subtrees and Wiener index of graphs. RAIRO. Operations Research, Tome 56 (2022) no. 4, pp. 2495-2511. doi: 10.1051/ro/2022118

[1] E. Andriantiana, S. Wagner and H. Wang, Greedy trees, subtrees and antichains. Electron. J. Comb. 20 (2013) P28. | MR | DOI

[2] E. Andriantiana, S. Wagner and H. Wang, Extremal problems for trees with given segment sequence. Discrete Appl. Math. 220 (2017) 20–34. | MR | DOI

[3] E. O. D. Andriantiana and H. Wang, Subtrees and independent subsets in unicyclic graphs and unicyclic graphs with fixed segment sequence. MATCH Commun. Math. Comput. Chem. 84 (2020) 537–566. | MR

[4] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications. Macmillan Press, New York (1976). | MR | DOI

[5] F. Buckley, Mean distance in line graphs. Congr. Numer. 32 (1981) 153–162. | MR

[6] R. Diestel, Graph Theory. Springer-Verlag, Berlin (2006). | MR

[7] A. A. Dobryinin, On the Wiener index of the forest induced by contraction of edges in a tree. MATCH Commun. Math. Comput. Chem. 86 (2021) 321–326. | MR

[8] A. A. Dobrynin and E. Estaji, Wiener index of certain families of hexagonal chains. J. Appl. Math. Comput. 59 (2019) 245–256. | MR | DOI

[9] A. A. Dobrynin, R. Entringer and I. Gutman, Wiener index of trees: theory and applications. Acta. Appl. Math. 66 (2001) 211–249. | MR | DOI

[10] A. A. Dobrynin, I. Gutman, S. Klavžar and P. Žigert, Wiener index of hexagonal systems. Acta Appl. Math. 72 (2002) 247–294. | MR | DOI

[11] H. Darabi, Y. Alizadeh, S. Klavžar and K. C. Das, On the relation between Wiener index and eccentricity of a graph. J. Comb. Optim. 41 (2021) 817–829. | MR | DOI

[12] K. C. Das and M. J. Nadjafi-Arani, On maximum Wiener index of trees and graphs with given radius. J. Comb. Optim. 34 (2017) 574–587. | MR | DOI

[13] K. C. Das, I. Gutman and M. J. Nadjafi-Arani, Relations between distance-based and degree-based topological indices. Appl. Math. Comput. 270 (2017) 142–147. | MR

[14] J. K. Doyle and J. E. Graver, Mean distance in a graph. Discrete Math. 7 (1977) 147–154. | MR | DOI

[15] V. Iršič and S. Klavžar, Strong geodetic problem on Cartesian products of graphs. RAIRO Oper. Res. 52 (2018) 205–216. | MR | Zbl | Numdam | DOI

[16] R. E. Jamison, On the average number of nodes in a subtree of a tree. J. Comb. Theory Ser. B 35 (1983) 207–223. | MR | DOI

[17] R. Kirk and H. Wang, Largest number of subtrees of trees with a given maximum degree. SIAM J. Discrete Math. 22 (2008) 985–995. | MR | DOI

[18] S. Klavžar and I. Gutman, Wiener number of vertex-weighted graphs and a chemical application. Discrete Appl. Math. 80 (1997) 73–81. | MR | DOI

[19] S. Klavžar and M. J. Nadjafi-Arani, Improved bounds on the difference between the Szeged index and the Wiener index of graphs. Eur. J. Comb. 39 (2014) 148–156. | MR | DOI

[20] S. Klavžar and M. J. Nadjafi-Arani, Wiener index in weighted graphs via unification of Θ * -classes. Eur. J. Comb. 36 (2014) 71–76. | MR | DOI

[21] S. Klavžar and M. J. Nadjafi-Arani, On the difference between the revised Szeged index and the Wiener index. Discrete Math. 333 (2014) 28–34. | MR | DOI

[22] M. Knor, S. Majstorović and R. Škrekovski, Graphs whose Wiener index does not change when a specific vertex is removed. Discrete Appl. Math. 238 (2018) 126–132. | MR | DOI

[23] S. Li and S. Wang, Further analysis on the total number of subtrees of trees. Electron. J. Comb. 19 (2012) P48. | MR | DOI

[24] J. Li, K. Xu, T. Zhang, H. Wang and S. Wagner, Maximum number of subtrees in cacti and block graphs. Aequat. Math. (2022). DOI: . | DOI | MR

[25] Z. Peng and B. Zhou, Minimum status of trees with given parameters. RAIRO Oper. Res. 55 (2021) S765–S785. | MR | Zbl | Numdam | DOI

[26] J. Plesník, On the sum of all distances in a graph or digraph. J. Graph Theory 8 (1984) 1–21. | MR | DOI

[27] N. Schmuck, S. Wagner and H. Wang, Greedy trees, caterpillars, and Wiener-type graph invariants. MATCH Commun. Math. Comput. Chem. 68 (2012) 273–292. | MR

[28] S. Spiro, The Wiener index of signed graphs. Appl. Math. Comput. 416 (2022) 126755. | MR

[29] L. A. Székely and H. Wang, On subtrees of trees. Adv. Appl. Math. 34 (2005) 138–155. | MR | DOI

[30] L. A. Székely and H. Wang, Binary trees with the largest number of subtrees. Discrete Appl. Math. 155 (2007) 374–385. | MR | DOI

[31] S. Wagner and H. Wang, Indistinguishable trees and graphs. Graphs Comb. 30 (2014) 1593–1605. | MR | DOI

[32] H. Wiener, Structrual determination of paraffin boiling points. J. Am. Chem. Soc. 69 (1947) 17–20. | DOI

[33] K. Xu, M. Liu, K. C. Das, I. Gutman and B. Furtula, A survey on graphs extremal with respect to distance-based topological indices. MATCH Commun. Math. Comput. Chem. 71 (2014) 461–508. | MR

[34] K. Xu, K. C. Das, S. Klavžar and H. Li, Comparison of Wiener index and Zagreb eccentricity indices. MATCH Commun. Math. Comput. Chem. 84 (2020) 595–610. | MR

[35] K. Xu and J. Li, H. Wang, The number of subtrees in graphs with given number of cut edges. Discrete Appl. Math. 304 (2021) 283–296. | MR | DOI

[36] K. Xu, M. Wang and J. Tian, Relations between Merrifield-Simmons and Wiener indices. MATCH Commun. Math. Comput. Chem. 85 (2021) 147–160. | MR

[37] K. Xu, K. C. Das, I. Gutman and M. Wang, Comparison Between Merrifield-Simmons Index and Wiener Index of Graphs. Acta Mathematica Sinica, English Series (2022). DOI: . | DOI | MR

[38] W. Yan and Y. N. Yeh, Enumeration of subtrees of trees. Theor. Comput. Sci. 369 (2006) 256–268. | MR | DOI

[39] X. M. Zhang, X. D. Zhang, D. Gray and H. Wang, The number of subtrees of trees with given degree sequence. J. Graph Theory 73 (2013) 280–295. | MR | DOI

Cité par Sources :