Maximum Zagreb index, minimum hyper-Wiener index and graph connectivity. (English) Zbl 1171.05350

Summary: We show that among all \(n\)-vertex graphs with edge or vertex connectivity \(k\), the graph \(G=K_k\vee (K_{1}+K_{n-k-1})\), the join of \(K_k\), the complete graph on \(k\) vertices, with the disjoint union of \(K_{1}\) and \(K_{n-k-1}\), is the unique graph with maximum sum of squares of vertex degrees. This graph is also the unique \(n\)-vertex graph with edge or vertex connectivity \(k\) whose hyper-Wiener index is minimum.


05C40 Connectivity
Full Text: DOI


[1] West, D., Introduction to Graph Theory (2001), Prentice Hall
[2] Wiener, H., Structural determination of paraffin boiling points, J. Amer. Chem. Soc., 69, 17-20 (1974)
[3] Randić, M., Novel molecular descriptor for structure-property studies, Chem. Phys. Lett., 211, 478-483 (1993)
[4] Klein, D.; Lukovits, I.; Gutman, I., On the definition of Hyper-Wiener index for cycle-containing structures, J. Chem. Inf. Comput. Phys. Chem. Sci., 35, 50-52 (1995)
[5] Gutman, I.; Trinajstić, N., Graph theory and molecular orbitals, Total \(\pi\) electron energy of alternant hydrocarbons, Chem. Phys. Lett., 17, 535-538 (1972)
[6] Gutman, I., Graphs with smallest sum of squares of vertex degrees, Kragujevac J. Math., 25, 51-54 (2003) · Zbl 1052.05024
[7] Das Kinkar, Ch., Maximizing the sum of the squares of the degrees of a graph, Discrete Math., 285, 57-66 (2004) · Zbl 1051.05033
[8] de Caen, D., An upper bound on the sum of squares of degrees in a graph, Discrete Math., 185, 245-248 (1998) · Zbl 0955.05059
[9] Nikiforov, V., The sum of the squares of degrees: Sharp asymptotics, Discrete Math., 307, 3187-3193 (2007) · Zbl 1127.05054
[10] Gutman, I.; Zhang, S., Graph connectivity and Wiener index, Bull. Acad. Serbe Sci. Arts Cl. Math. Natur., 133, 1-5 (2006) · Zbl 1150.05327
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.