Cacti with \(n\)-vertices and \(t\) cycles having extremal Wiener index. (English) Zbl 1372.05058
Summary: The Wiener index \(W(G)\) of a connected graph \(G\) is the sum of distances between all pairs of vertices of \(G\). A connected graph \(G\) is said to be a cactus if each of its blocks is either a cycle or an edge. Let \(\mathcal{G}_{n,t}\) be the set of all \(n\)-vertex cacti containing exactly \(t\) cycles. H. Liu and M. Lu [MATCH Commun. Math. Comput. Chem. 58, No. 1, 183–194 (2007; Zbl 1164.05043)] determined the unique graph in \(\mathcal{G}_{n,t}\) with the minimum Wiener index. We now establish a sharp upper bound on the Wiener index of graphs in \(\mathcal{G}_{n,t}\) and identify the corresponding extremal graphs.
Citations:
Zbl 1164.05043References:
| [1] | Bondy, J. A.; Murty, U. S.R., Graph Theory (2008), Springer: Springer New York · Zbl 1134.05001 |
| [2] | Bose, S. S.; Nath, M.; Paul, S., On the distance spectral radius of cacti, Linear Algebra Appl., 437, 2128-2141 (2012) · Zbl 1247.05133 |
| [3] | Buckley, F.; Harary, F., Distance in Graphs (1990), Addison-Wesley: Addison-Wesley Redwood · Zbl 0688.05017 |
| [4] | Dobrynin, A.; Entringer, R. C.; Gutman, I., Wiener index of trees: theory and applications, Acta Appl. Math., 66, 211-249 (2001) · Zbl 0982.05044 |
| [5] | Dobrynin, A.; Gutman, I.; Klavžar, S.; Žigert, P., Wiener index of hexagonal systems, Acta Appl. Math., 72, 247-294 (2002) · Zbl 0993.05059 |
| [6] | Elenbogen, B.; Fink, J. F., Distance distributions for graphs modeling computer networks, Discrete Appl. Math., 155, 2612-2624 (2007) · Zbl 1126.05044 |
| [7] | Entringer, R. C., Distance in graphs: trees, J. Comb. Math. Comb. Comput., 24, 65-84 (1997) · Zbl 0880.05029 |
| [8] | Entringer, R. C.; Jackson, D. E.; Snyder, D. A., Distance in graphs, Czechoslovak Math. J., 26, 283-296 (1976) · Zbl 0329.05112 |
| [9] | Gutman, I., On distances in some bipartite graphs, Publ. Inst. Math. (Beograd), 43, 3-8 (1988) · Zbl 0645.05046 |
| [10] | Gutman, I.; Polansky, O. E., Mathematical Concepts in Organic Chemistry (1986), Springer: Springer Berlin · Zbl 0657.92024 |
| [11] | Harary, F., Status and contrastatus, Sociometry, 22, 233-243 (1959) |
| [12] | Hoffman, A. J.; Smith, J. H., On the spectral radii of topological equivalent graphs, (Fiedler, M., Recent Advances in Graph Theory (1975), Academia: Academia Prague), 273-281 · Zbl 0327.05125 |
| [13] | Knor, M.; Škrekovski, R.; Tepeh, A., Mathematical aspects of wiener index, Ars. Math. Contemp., 11, 327-352 (2016) · Zbl 1355.05099 |
| [14] | Liu, H. Q.; Lu, M., A unified approach to extremal cacti for different indices, MATCH Commun. Math. Comput. Chem., 58, 183-194 (2007) · Zbl 1164.05043 |
| [15] | Plesník, J., On the sum of distances in a graph or digraph, J. Graph Theory, 8, 1-21 (1984) · Zbl 0552.05048 |
| [16] | Polansky, O. E.; Bonchev, D., The Wiener number of graphs I: general theory and changes due to graph operations, MATCH Commun. Math. Comput. Chem., 21, 133-186 (1986) · Zbl 0603.05045 |
| [17] | Polansky, O. E.; Bonchev, D., Theory of the Wiener number of graphs II: Transfer graphs and some of their metric properties, MATCH Commun. Math. Comput. Chem., 25, 3-39 (1990) · Zbl 0768.05091 |
| [18] | Rouvray, D. H., The rich legacy of half century of the Wiener index, (Rouvray, D. H.; King, R. B., Topology in Chemistry -Discrete Mathematics of Molecules (2002), Horwood: Horwood Chichester), 16-37 · Zbl 1207.92056 |
| [19] | Soltés, L., Transmission in graphs: a bound and vertex removing, Math. Slovaca, 41, 11-16 (1991) · Zbl 0765.05097 |
| [20] | Tang, Z.; Deng, H., The graphs with minimal and maximal Wiener indices among a class of bicyclic graphs, J. Nat. Sci. Hunan Norm. Univ., 31, 1, 27-30 (2008) · Zbl 1174.05355 |
| [21] | Wiener, H., Structural determination of paraffin boiling point, J. Am. Chem. Soc., 69, 17-20 (1947) |
| [22] | Xu, K.; Liu, M.; Das, K. C.; Gutman, I.; Furtula, B., A survey on graphs extremal with respect to distance-based topological indices, MATCH Commun. Math. Comput. Chem., 71, 461-508 (2014) · Zbl 1464.05140 |
| [23] | Yu, G. H.; Feng, L. H., On the Wiener index of unicyclic graphs with given girth, Ars. Combin., 94, 361-369 (2010) · Zbl 1238.92073 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
