Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
cut-vertex; distance; pendant vertex; unicyclic graph; Wiener index
cut-vertex; distance; pendant vertex; unicyclic graph; Wiener index
Summary:
The Wiener index of a connected graph is defined as the sum of the distances between all unordered pairs of its vertices. We characterize the graphs which extremize the Wiener index among all graphs on $n$ vertices with $k$ pendant vertices. We also characterize the graph which minimizes the Wiener index over the graphs on $n$ vertices with $s$ cut-vertices.
References:
[1] Althöfer, I.: Average distances in undirected graphs and the removal of vertices. J. Comb. Theory, Ser. B 48 (1990), 140-142. DOI 10.1016/0095-8956(90)90136-N | MR 1047559 | Zbl 0688.05045
[2] Balakrishnan, R., Sridharan, N., Iyer, K. Viswanathan: Wiener index of graphs with more than one cut-vertex. Appl. Math. Lett. 21 (2008), 922-927. DOI 10.1016/j.aml.2007.10.003 | MR 2436525 | Zbl 1152.05322
[3] Buckley, F., Harary, F.: Distance in Graphs. Addison-Wesley, Redwood (1990). MR 1045632 | Zbl 0688.05017
[4] Dankelmann, P.: Average distance and independence number. Discrete Appl. Math. 51 (1994), 75-83. DOI 10.1016/0166-218X(94)90095-7 | MR 1279621 | Zbl 0803.05020
[5] Doyle, J. K., Graver, J. E.: Mean distance in a graph. Discrete Math. 17 (1977), 147-154. DOI 10.1016/0012-365X(77)90144-3 | MR 0485476 | Zbl 0361.05045
[6] Entringer, R. C., Jackson, D. E., Snyder, D. A.: Distance in graphs. Czech. Math. J. 26 (1976), 283-296. DOI 10.21136/CMJ.1976.101401 | MR 0543771 | Zbl 0329.05112
[7] Gutman, I.: On distances in some bipartite graphs. Publ. Inst. Math., Nouv. Sér. 43 (1988), 3-8. MR 0962249 | Zbl 0645.05046
[8] Gutman, I., Cruz, R., Rada, J.: Wiener index of Eulerian graphs. Discrete Appl. Math. 162 (2014), 247-250. DOI 10.1016/j.dam.2013.08.024 | MR 3128526 | Zbl 1298.05093
[9] Jelen, F., Triesch, E.: Superdominance order and distance of trees with bounded maximum degree. Discrete Appl. Math. 125 (2003), 225-233. DOI 10.1016/s0166-218X(02)00195-6 | MR 1943114 | Zbl 1009.05052
[10] Liu, H., Lu, M.: A unified approach to extremal cacti for different indices. MATCH Commun. Math. Comput. Chem. 58 (2007), 183-194. MR 2335488 | Zbl 1164.05043
[11] Liu, H., Pan, X.-F.: On the Wiener index of trees with fixed diameter. MATCH Commun. Math. Comput. Chem. 60 (2008), 85-94. MR 2423499 | Zbl 1199.05092
[12] Plesn{'ık, J.: On the sum of all distances in a graph or digraph. J. Graph Theory 8 (1984), 1-21. DOI 10.1002/jgt.3190080102 | MR 0732013 | Zbl 0552.05048
[13] Shi, R.: The average distance of trees. Syst. Sci. Math. Sci. 6 (1993), 18-24. MR 1215913 | Zbl 0802.05036
[14] Stevanović, D.: Maximizing Wiener index of graphs with fixed maximum degree. MATCH Commun. Math. Comput. Chem. 60 (2008), 71-83. MR 2423498 | Zbl 1274.05137
[15] Tan, S.-W.: The minimum Wiener index of unicyclic graphs with a fixed diameter. J. Appl. Math. Comput. 56 (2018), 93-114. DOI 10.1007/s12190-016-1063-2 | MR 3770377 | Zbl 1390.05045
[16] Tan, S.-W., Wang, Q.-L., Lin, Y.: The Wiener index of unicyclic graphs given number of pendant vertices or cut vertices. J. Appl. Math. Comput. 55 (2017), 1-24. DOI 10.1007/s12190-016-1022-y | MR 3694934 | Zbl 1373.05056
[17] Wang, H.: The extremal values of the Wiener index of a tree with given degree sequence. Discrete Appl. Math. 156 (2008), 2647-2654. DOI 10.1016/j.dam.2007.11.005 | MR 2451087 | Zbl 1155.05020
[18] West, D. B.: Introduction to Graph Theory. Prentice Hall, Upper Saddle River (1996). MR 1367739 | Zbl 0845.05001
[19] Wiener, H.: Structural determination of paraffin boiling points. J. Am. Chem. Soc. 69 (1947), 17-20. DOI 10.1021/ja01193a005
[20] Winkler, P.: Mean distance in a tree. Discrete Appl. Math. 27 (1990), 179-185. DOI 10.1016/0166-218X(90)90137-2 | MR 1055599 | Zbl 0742.05032
[21] Yeh, Y.-N., Gutman, I.: On the sum of all distances in composite graphs. Discrete Math. 135 (1994), 359-365. DOI 10.1016/0012-365X(93)E0092-I | MR 1310892 | Zbl 0814.05033
[22] Yu, G., Feng, L.: On the Wiener index of unicyclic graphs with given girth. Ars Comb. 94 (2010), 361-369. MR 2599747 | Zbl 1238.92073
[23] Zhang, X.-D., Xiang, Q.-Y., Xu, L.-Q., Pan, R.-Y.: The Wiener index of trees with given degree sequences. MATCH Commun. Math. Comput. Chem. 60 (2008), 623-644. MR 2457876 | Zbl 1195.05022
Search
Partner of
