EMIS ELibM Electronic Journals Bulletin, Classe des Sciences Mathématiques et Naturelles, Sciences mathématiques naturelles / sciences mathematiques
Vol. CXXXIII, No. 31, pp. 1–5 (2006)

Next Article

Contents of this Issue

Other Issues

ELibM Journals

ELibM Home

EMIS Home

Pick a mirror

 		 

Graph connectivity and Wiener index

I. Gutman and S. Zhang

Faculty of Science, University of Kragujevac, P. O. Box 60, 34000 Kragujevac, Serbia
Department of Applied Mathematics, Northwestern Polytechnical University, Xi'an, Shaanxi 710072, P. R. China

Abstract: The graphs with a given number $n$ of vertices and given (vertex or edge) connectivity $k$ , having minimum Wiener index are determined. In both cases this is $K_k+(K_1 \cup K_{n-k-1})$ , the graph obtained by connecting all vertices of the complete graph $K_k$ with all vertices of the graph whose two components are $K_{n-k-1}$ and $K_1$ .

Keywords: graph connectivity, vertex–connectivity, edge–connectivity, Wiener index; extremal graphs

Classification (MSC2000): 05C12, 05C40, 05C35

Full text of the article: (for faster download, first choose a mirror)

Electronic fulltext finalized on: 10 Jun 2006. This page was last modified: 16 Nov 2007.

© 2006 Mathematical Institute of the Serbian Academy of Science and Arts
© 2006–2007 ELibM and FIZ Karlsruhe / Zentralblatt MATH for the EMIS Electronic Edition