Geodesic
Wiener index of graphs with fixed number of pendant or cut-vertices
Czechoslovak Mathematical Journal, Tome 72 (2022) no. 2, pp. 411-431
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.21136/CMJ.2022.0515-20
Classification : 05C05, 05C12, 05C35
Keywords: cut-vertex; distance; pendant vertex; unicyclic graph; Wiener index 
@article{10_21136_CMJ_2022_0515_20,
     author = {Pandey, Dinesh and Patra, Kamal Lochan},
     title = {Wiener index of graphs with fixed number of pendant or cut-vertices},
     journal = {Czechoslovak Mathematical Journal},
     pages = {411--431},
     year = {2022},
     volume = {72},
     number = {2},
     doi = {10.21136/CMJ.2022.0515-20},
     mrnumber = {4412767},
     zbl = {07547212},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2022.0515-20/}
}
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
SP  - 411
EP  - 431
VL  - 72
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2022.0515-20/
DO  - 10.21136/CMJ.2022.0515-20
LA  - en
ID  - 10_21136_CMJ_2022_0515_20
ER  - 
%0 Journal Article
%A Pandey, Dinesh
%A Patra, Kamal Lochan
%T Wiener index of graphs with fixed number of pendant or cut-vertices
%J Czechoslovak Mathematical Journal
%D 2022
%P 411-431
%V 72
%N 2
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2022.0515-20/
%R 10.21136/CMJ.2022.0515-20
%G en
%F 10_21136_CMJ_2022_0515_20
Pandey, Dinesh; Patra, Kamal Lochan. Wiener index of graphs with fixed number of pendant or cut-vertices. Czechoslovak Mathematical Journal, Tome 72 (2022) no. 2, pp. 411-431. doi: 10.21136/CMJ.2022.0515-20

[1] Althöfer, I.: Average distances in undirected graphs and the removal of vertices. J. Comb. Theory, Ser. B 48 (1990), 140-142. | DOI | MR | JFM

[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 | MR | JFM

[3] Buckley, F., Harary, F.: Distance in Graphs. Addison-Wesley, Redwood (1990). | MR | JFM

[4] Dankelmann, P.: Average distance and independence number. Discrete Appl. Math. 51 (1994), 75-83. | DOI | MR | JFM

[5] Doyle, J. K., Graver, J. E.: Mean distance in a graph. Discrete Math. 17 (1977), 147-154. | DOI | MR | JFM

[6] Entringer, R. C., Jackson, D. E., Snyder, D. A.: Distance in graphs. Czech. Math. J. 26 (1976), 283-296. | DOI | MR | JFM

[7] Gutman, I.: On distances in some bipartite graphs. Publ. Inst. Math., Nouv. Sér. 43 (1988), 3-8. | MR | JFM

[8] Gutman, I., Cruz, R., Rada, J.: Wiener index of Eulerian graphs. Discrete Appl. Math. 162 (2014), 247-250. | DOI | MR | JFM

[9] Jelen, F., Triesch, E.: Superdominance order and distance of trees with bounded maximum degree. Discrete Appl. Math. 125 (2003), 225-233. | DOI | MR | JFM

[10] Liu, H., Lu, M.: A unified approach to extremal cacti for different indices. MATCH Commun. Math. Comput. Chem. 58 (2007), 183-194. | MR | JFM

[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 | JFM

[12] Plesn{'ık, J.: On the sum of all distances in a graph or digraph. J. Graph Theory 8 (1984), 1-21. | DOI | MR | JFM

[13] Shi, R.: The average distance of trees. Syst. Sci. Math. Sci. 6 (1993), 18-24. | MR | JFM

[14] Stevanović, D.: Maximizing Wiener index of graphs with fixed maximum degree. MATCH Commun. Math. Comput. Chem. 60 (2008), 71-83. | MR | JFM

[15] Tan, S.-W.: The minimum Wiener index of unicyclic graphs with a fixed diameter. J. Appl. Math. Comput. 56 (2018), 93-114. | DOI | MR | JFM

[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 | MR | JFM

[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 | MR | JFM

[18] West, D. B.: Introduction to Graph Theory. Prentice Hall, Upper Saddle River (1996). | MR | JFM

[19] Wiener, H.: Structural determination of paraffin boiling points. J. Am. Chem. Soc. 69 (1947), 17-20. | DOI

[20] Winkler, P.: Mean distance in a tree. Discrete Appl. Math. 27 (1990), 179-185. | DOI | MR | JFM

[21] Yeh, Y.-N., Gutman, I.: On the sum of all distances in composite graphs. Discrete Math. 135 (1994), 359-365. | DOI | MR | JFM

[22] Yu, G., Feng, L.: On the Wiener index of unicyclic graphs with given girth. Ars Comb. 94 (2010), 361-369. | MR | JFM

[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 | JFM

Cité par Sources :