Sufficient conditions for maximally edge-connected and super-edge-connected

Document Type : Original paper

Authors

1 RWTH Aachen University

2 Anhui University of Finance and Economics

Abstract

Let $G$ be a connected graph with minimum degree $\delta$ and edge-connectivity $\lambda$. A graph is maximally edge-connected if $\lambda=\delta$, and it is  super-edge-connected if every minimum edge-cut is trivial; that is, if every minimum edge-cut consists of edges incident with a vertex of minimum degree. In this paper, we show that a connected graph or a connected triangle-free graph is maximally edge-connected  or super-edge-connected if the number of edges is large enough.

Keywords

Main Subjects

References

[1] D. Bauer, F. Boesch, C. Suffel, and R. Tindell, Connectivity extremal problems and the design of reliable probabilistic networks, The theory and application of graphs, Wiley, New York (1981), 45–54.
[2] G. Chartrand, A graph-theoretic approach to a communications problem, SIAM J. Appl. Math. 14 (1966), no. 4, 778–781.
[3] A. Hellwig and L. Volkmann, Maximally edge-connected and vertexconnected graphs and digraphs: A survey, Discrete Math. 308 (2008), no. 15, 3265–3296.
[4] A.K. Kelmans, Asymptotic formulas for the probability of k-connectedness of random graphs, Theory Probab. Appl. 17 (1972), no. 2, 243–254.
[5] W. Mantel, Problem 28, Wiskundige Opgaven 10 (1907), 60–61.
[6] P. Turán, On an extremal problem in graph theory (hungarian), Mat. Fiz. Lapok 48 (1941), 436–452.
 
Communications in Combinatorics and Optimization
Volume 2, Issue 1
June 2017
Pages 35-41

Files

Share

How to cite

Statistics