| 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:
|
2024-07-01 |
| 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 |
| . |
