Article
| Title: | Wiener index of graphs with fixed number of pendant or cut-vertices (English) |
| Author: | Pandey, Dinesh |
| Author: | Patra, Kamal Lochan |
| Language: | English |
| Journal: | Czechoslovak Mathematical Journal |
| ISSN: | 0011-4642 (print) |
| ISSN: | 1572-9141 (online) |
| Volume: | 72 |
| Issue: | 2 |
| Year: | 2022 |
| Pages: | 411-431 |
| Summary lang: | English |
| . | |
| Category: | math |
| . | |
| 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. (English) |
| Keyword: | cut-vertex |
| Keyword: | distance |
| Keyword: | pendant vertex |
| Keyword: | unicyclic graph |
| Keyword: | Wiener index |
| MSC: | 05C05 |
| MSC: | 05C12 |
| MSC: | 05C35 |
| idZBL: | Zbl 07547212 |
| idMR: | MR4412767 |
| DOI: | 10.21136/CMJ.2022.0515-20 |
| . | |
| Date available: | 2022-04-21T19:01:15Z |
| Last updated: | 2022-09-08 |
| Stable URL: | http://hdl.handle.net/10338.dmlcz/150409 |
| . | |
| Reference: | [1] Althöfer, I.: Average distances in undirected graphs and the removal of vertices.J. Comb. Theory, Ser. B 48 (1990), 140-142. Zbl 0688.05045, MR 1047559, 10.1016/0095-8956(90)90136-N |
| Reference: | [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. Zbl 1152.05322, MR 2436525, 10.1016/j.aml.2007.10.003 |
| Reference: | [3] Buckley, F., Harary, F.: Distance in Graphs.Addison-Wesley, Redwood (1990). Zbl 0688.05017, MR 1045632 |
| Reference: | [4] Dankelmann, P.: Average distance and independence number.Discrete Appl. Math. 51 (1994), 75-83. Zbl 0803.05020, MR 1279621, 10.1016/0166-218X(94)90095-7 |
| Reference: | [5] Doyle, J. K., Graver, J. E.: Mean distance in a graph.Discrete Math. 17 (1977), 147-154. Zbl 0361.05045, MR 0485476, 10.1016/0012-365X(77)90144-3 |
| Reference: | [6] Entringer, R. C., Jackson, D. E., Snyder, D. A.: Distance in graphs.Czech. Math. J. 26 (1976), 283-296. Zbl 0329.05112, MR 0543771, 10.21136/CMJ.1976.101401 |
| Reference: | [7] Gutman, I.: On distances in some bipartite graphs.Publ. Inst. Math., Nouv. Sér. 43 (1988), 3-8. Zbl 0645.05046, MR 0962249 |
| Reference: | [8] Gutman, I., Cruz, R., Rada, J.: Wiener index of Eulerian graphs.Discrete Appl. Math. 162 (2014), 247-250. Zbl 1298.05093, MR 3128526, 10.1016/j.dam.2013.08.024 |
| Reference: | [9] Jelen, F., Triesch, E.: Superdominance order and distance of trees with bounded maximum degree.Discrete Appl. Math. 125 (2003), 225-233. Zbl 1009.05052, MR 1943114, 10.1016/s0166-218X(02)00195-6 |
| Reference: | [10] Liu, H., Lu, M.: A unified approach to extremal cacti for different indices.MATCH Commun. Math. Comput. Chem. 58 (2007), 183-194. Zbl 1164.05043, MR 2335488 |
| Reference: | [11] Liu, H., Pan, X.-F.: On the Wiener index of trees with fixed diameter.MATCH Commun. Math. Comput. Chem. 60 (2008), 85-94. Zbl 1199.05092, MR 2423499 |
| Reference: | [12] Plesn{'ık, J.: On the sum of all distances in a graph or digraph.J. Graph Theory 8 (1984), 1-21. Zbl 0552.05048, MR 0732013, 10.1002/jgt.3190080102 |
| Reference: | [13] Shi, R.: The average distance of trees.Syst. Sci. Math. Sci. 6 (1993), 18-24. Zbl 0802.05036, MR 1215913 |
| Reference: | [14] Stevanović, D.: Maximizing Wiener index of graphs with fixed maximum degree.MATCH Commun. Math. Comput. Chem. 60 (2008), 71-83. Zbl 1274.05137, MR 2423498 |
| Reference: | [15] Tan, S.-W.: The minimum Wiener index of unicyclic graphs with a fixed diameter.J. Appl. Math. Comput. 56 (2018), 93-114. Zbl 1390.05045, MR 3770377, 10.1007/s12190-016-1063-2 |
| Reference: | [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. Zbl 1373.05056, MR 3694934, 10.1007/s12190-016-1022-y |
| Reference: | [17] Wang, H.: The extremal values of the Wiener index of a tree with given degree sequence.Discrete Appl. Math. 156 (2008), 2647-2654. Zbl 1155.05020, MR 2451087, 10.1016/j.dam.2007.11.005 |
| Reference: | [18] West, D. B.: Introduction to Graph Theory.Prentice Hall, Upper Saddle River (1996). Zbl 0845.05001, MR 1367739 |
| Reference: | [19] Wiener, H.: Structural determination of paraffin boiling points.J. Am. Chem. Soc. 69 (1947), 17-20. 10.1021/ja01193a005 |
| Reference: | [20] Winkler, P.: Mean distance in a tree.Discrete Appl. Math. 27 (1990), 179-185. Zbl 0742.05032, MR 1055599, 10.1016/0166-218X(90)90137-2 |
| Reference: | [21] Yeh, Y.-N., Gutman, I.: On the sum of all distances in composite graphs.Discrete Math. 135 (1994), 359-365. Zbl 0814.05033, MR 1310892, 10.1016/0012-365X(93)E0092-I |
| Reference: | [22] Yu, G., Feng, L.: On the Wiener index of unicyclic graphs with given girth.Ars Comb. 94 (2010), 361-369. Zbl 1238.92073, MR 2599747 |
| Reference: | [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. Zbl 1195.05022, MR 2457876 |
| . |
Fulltext not available (moving wall 24 months)
Search
Partner of
