Abstract
Let \(G\) be a connected graph with order \(n,\) minimum degree \(\delta =\delta (G)\) and edge-connectivity \(\lambda =\lambda (G).\) A graph \(G\) is maximally edge-connected if \(\lambda =\delta .\) In this paper, we present two sufficient conditions for graphs to be maximally edge-connected, which generalize two results recently proved by P. Dankelmann, A. Hellwig and L. Volkmann. The extremal graphs are also characterized.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bondy JA, Murty USR (1976) Graph theory with applications. Elsevier, New York
Chartrand G (1966) A graph-theoretic approach to a communications problem. SIAM J Appl Math 14:778–781
Chartrand G, Harary F (1968) Graphs with prescribed connectivities. In: Erdös P, Katona G (eds) Theory of graphs. Academic Press, London, pp 61–63
Dankelmann P, Hellwig A, Volkmann L (2009) Inverse degree and edge connectivity. Discret Math 309:2943–2947
Daneklmann P, Volkmann L (1995) New sufficient conditions for equality of minimum degree and edge-connectivity. Ars Combinatoria 40:270–278
Dankelmann P, Volkmann L (1997) Degree sequence condition for maximally edge-connectivity graphs and digraphs. J Graph Theory 26:27–34
Dankelmann P, Swart HC, van den Berg P (2008) Diameter and inverse degree. Discret Math 308:670–673
Dankelmann P, Volkmann L (2000) Degree sequence conditions for maximally edge-connected graphs depending on the clique number. Discret Math 211:217–223
Erdös P, Pach J, Spencer J (1988) On the mean distance between points of a graph. Congr Numer 64:121–124
Fajtlowicz S (1987) On conjectures of graffiti II. Congr Numer 60:189–197
Fiol MA (1993) The connectivity of large digraphs and graphs. J Graph Theory 17:31–45
Febrega J, Fiol MA (1989) Maximally connected digraphs. J Graph Theory 13:657–668
Febrega J, Fiol MA (1996) Bipartite graphs and digraphs with maximally connectivity. Discret Appl Math 69:271–279
Goldsmith DL, White AT (1978) On graphs with equal edge-connectivity and minimum degree. Discrete Math 23:31–36
Hu Y et al (2005) On molecular graphs with smallest and greatest Zeroth-order general Randić index. MATCH Commun Math Comput Chem 54:425–434
Hua H, Deng H (2006) On Uincycle graphs with maximum and minimum Zeroth-order general Randić index, J Math Chem
Li X, Zheng J (2005) An unified approach to the extremal trees for different indices. MATCH Commun Math Comput Chem 51:195–208
Li X, Zhao H (2004) Trees with the first three smallest and largest generalized topological indices. MATCH Commun Math Comput Chem 51:205–210
Lesniak L (1974) Results on the edge-connectivity of graphs. Discret Math 8:35l–354
Lin A, Luo R, Zha X (2009) On sharp bounds of the Zeroth-order Randić index of certain unicycle graphs. Appl Math Lett 22:585–589
Plesník J (1975) Critical graphs of given diamter. Acta Fac Rer Nat Univ Comenianae Math 30:71–93
Plesník J, Znám S (1989) On equality of edge-connectivity and minimum degree of a graph. Arch Math (Brno) 25:19–25
Soneoka T, Nakada H, Imase M (1987) Sufficient conditions for maximally connected dense graphs. Discret Math 63:53–66
Turán P (1941) Eine extremalaufgabe aus der graphentheorie. Mat Fiz Lapook 48:436–452
Whitney H (1932) Congruent graphs and the connectivity of graphs. Amer J Math 54:150–168
Xu J (1994) A sufficient condition for equality of arc-connectivity and minimum degree of a digraph. Discret Math 133:315–318
Acknowledgments
This work is supported by the Natural Science Funds of China (No. 11071016 and No: 11171129) and by the Beijing Natural Science Foundation (No. 1102015).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Su, G., Xiong, L., Su, X. et al. Maximally edge-connected graphs and Zeroth-order general Randić index for \(\alpha \le -1\) . J Comb Optim 31, 182–195 (2016). https://doi.org/10.1007/s10878-014-9728-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-014-9728-y