Wiener index of graphs with fixed number of pendant or cut-vertices

Dinesh Pandey; Kamal Lochan Patra

Czechoslovak Mathematical Journal (2022)

  • Volume: 72, Issue: 2, page 411-431
  • ISSN: 0011-4642

Abstract

top
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.

How to cite

top

Pandey, Dinesh, and Patra, Kamal Lochan. "Wiener index of graphs with fixed number of pendant or cut-vertices." Czechoslovak Mathematical Journal 72.2 (2022): 411-431. <http://eudml.org/doc/298315>.

@article{Pandey2022,
abstract = {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.},
author = {Pandey, Dinesh, Patra, Kamal Lochan},
journal = {Czechoslovak Mathematical Journal},
keywords = {cut-vertex; distance; pendant vertex; unicyclic graph; Wiener index},
language = {eng},
number = {2},
pages = {411-431},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Wiener index of graphs with fixed number of pendant or cut-vertices},
url = {http://eudml.org/doc/298315},
volume = {72},
year = {2022},
}

TY - JOUR
AU - Pandey, Dinesh
AU - Patra, Kamal Lochan
TI - Wiener index of graphs with fixed number of pendant or cut-vertices
JO - Czechoslovak Mathematical Journal
PY - 2022
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 72
IS - 2
SP - 411
EP - 431
AB - 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.
LA - eng
KW - cut-vertex; distance; pendant vertex; unicyclic graph; Wiener index
UR - http://eudml.org/doc/298315
ER -

References

top
  1. Althöfer, I., 10.1016/0095-8956(90)90136-N, J. Comb. Theory, Ser. B 48 (1990), 140-142. (1990) Zbl0688.05045MR1047559DOI10.1016/0095-8956(90)90136-N
  2. Balakrishnan, R., Sridharan, N., Iyer, K. Viswanathan, 10.1016/j.aml.2007.10.003, Appl. Math. Lett. 21 (2008), 922-927. (2008) Zbl1152.05322MR2436525DOI10.1016/j.aml.2007.10.003
  3. Buckley, F., Harary, F., Distance in Graphs, Addison-Wesley, Redwood (1990). (1990) Zbl0688.05017MR1045632
  4. Dankelmann, P., 10.1016/0166-218X(94)90095-7, Discrete Appl. Math. 51 (1994), 75-83. (1994) Zbl0803.05020MR1279621DOI10.1016/0166-218X(94)90095-7
  5. Doyle, J. K., Graver, J. E., 10.1016/0012-365X(77)90144-3, Discrete Math. 17 (1977), 147-154. (1977) Zbl0361.05045MR0485476DOI10.1016/0012-365X(77)90144-3
  6. Entringer, R. C., Jackson, D. E., Snyder, D. A., 10.21136/CMJ.1976.101401, Czech. Math. J. 26 (1976), 283-296. (1976) Zbl0329.05112MR0543771DOI10.21136/CMJ.1976.101401
  7. Gutman, I., On distances in some bipartite graphs, Publ. Inst. Math., Nouv. Sér. 43 (1988), 3-8. (1988) Zbl0645.05046MR0962249
  8. Gutman, I., Cruz, R., Rada, J., 10.1016/j.dam.2013.08.024, Discrete Appl. Math. 162 (2014), 247-250. (2014) Zbl1298.05093MR3128526DOI10.1016/j.dam.2013.08.024
  9. Jelen, F., Triesch, E., 10.1016/s0166-218X(02)00195-6, Discrete Appl. Math. 125 (2003), 225-233. (2003) Zbl1009.05052MR1943114DOI10.1016/s0166-218X(02)00195-6
  10. Liu, H., Lu, M., A unified approach to extremal cacti for different indices, MATCH Commun. Math. Comput. Chem. 58 (2007), 183-194. (2007) Zbl1164.05043MR2335488
  11. Liu, H., Pan, X.-F., On the Wiener index of trees with fixed diameter, MATCH Commun. Math. Comput. Chem. 60 (2008), 85-94. (2008) Zbl1199.05092MR2423499
  12. Plesn{'ık, J., 10.1002/jgt.3190080102, J. Graph Theory 8 (1984), 1-21. (1984) Zbl0552.05048MR0732013DOI10.1002/jgt.3190080102
  13. Shi, R., The average distance of trees, Syst. Sci. Math. Sci. 6 (1993), 18-24. (1993) Zbl0802.05036MR1215913
  14. Stevanović, D., Maximizing Wiener index of graphs with fixed maximum degree, MATCH Commun. Math. Comput. Chem. 60 (2008), 71-83. (2008) Zbl1274.05137MR2423498
  15. Tan, S.-W., 10.1007/s12190-016-1063-2, J. Appl. Math. Comput. 56 (2018), 93-114. (2018) Zbl1390.05045MR3770377DOI10.1007/s12190-016-1063-2
  16. Tan, S.-W., Wang, Q.-L., Lin, Y., 10.1007/s12190-016-1022-y, J. Appl. Math. Comput. 55 (2017), 1-24. (2017) Zbl1373.05056MR3694934DOI10.1007/s12190-016-1022-y
  17. Wang, H., 10.1016/j.dam.2007.11.005, Discrete Appl. Math. 156 (2008), 2647-2654. (2008) Zbl1155.05020MR2451087DOI10.1016/j.dam.2007.11.005
  18. West, D. B., Introduction to Graph Theory, Prentice Hall, Upper Saddle River (1996). (1996) Zbl0845.05001MR1367739
  19. Wiener, H., 10.1021/ja01193a005, J. Am. Chem. Soc. 69 (1947), 17-20. (1947) DOI10.1021/ja01193a005
  20. Winkler, P., 10.1016/0166-218X(90)90137-2, Discrete Appl. Math. 27 (1990), 179-185. (1990) Zbl0742.05032MR1055599DOI10.1016/0166-218X(90)90137-2
  21. Yeh, Y.-N., Gutman, I., 10.1016/0012-365X(93)E0092-I, Discrete Math. 135 (1994), 359-365. (1994) Zbl0814.05033MR1310892DOI10.1016/0012-365X(93)E0092-I
  22. Yu, G., Feng, L., On the Wiener index of unicyclic graphs with given girth, Ars Comb. 94 (2010), 361-369. (2010) Zbl1238.92073MR2599747
  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. (2008) Zbl1195.05022MR2457876

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.