ON SIZE, ORDER, DIAMETER AND VERTEX-CONNECTIVITY

Year 2019, Volume: 1 Issue: 1, 21 - 24, 02.01.2019

Sheunesu Munyira Simon Mukwembi

Abstract

Let G be a nite connected graph. We give an asymptotically sharp upper bound on the size of G in terms of its order, diameter and vertex-connectivity. The result is a strengthening of an old classical theorem of Ore [5] if vertex-connectivity is prescribed and constant.

Keywords

size, vertex-connectivity, diameter

References

• F.R.K. Chung, The average distance and the independence number, J. Graph Theory. 12 (1988) 229-235.
• P. Dankelmann, G.S. Domke, W. Goddard, P. Grobler J.H. Hattingh, H.C Swart, Maximum sizes of graphs with given domination parameters, DiscreteMath. 281 (2004) 137{148.
• P. Dankelmann, L. Volkmann, Minimum size of a graph or digraph of given radius, Inform. Process. Lett. 109(2009), 971{973.
• S. Mukwembi, On size, order, diameter and minimum degree, Indian J. Pure Appl. Math. 44 (2013) 467{472.
• O. Ore, Diameters in graphs, J. Combin. Theory 5 (1968) 75{81.Z. Tao, X. Junming, L. Jun, On diameters and average distance of graphs, Transactions 8 (2004) 1{6.
• A. Tripathi, S. Vijay, On the least size of a graph with a given degree set, Discrete Appl. Math. 154 (2006) 2530{2536.
• V. Vizing, The number of edges in a graph of given radius, Soviet. Math. Dokl.8 (1967) 535-536.