تعداد نشریات | 5 |
تعداد شمارهها | 108 |
تعداد مقالات | 1,228 |
تعداد مشاهده مقاله | 1,146,445 |
تعداد دریافت فایل اصل مقاله | 1,005,001 |
Sufficient conditions for maximally edge-connected and super-edge-connected | ||
Communications in Combinatorics and Optimization | ||
مقاله 4، دوره 2، شماره 1، شهریور 2017، صفحه 35-41 اصل مقاله (385.18 K) | ||
نوع مقاله: Original paper | ||
شناسه دیجیتال (DOI): 10.22049/cco.2017.13594 | ||
نویسندگان | ||
Lutz Volkmann* 1؛ Zhen-Mu Hong2 | ||
1RWTH Aachen University | ||
2Anhui University of Finance and Economics | ||
چکیده | ||
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. | ||
کلیدواژهها | ||
edge-connectivity؛ Maximally edge-connected graphs؛ Super-edge-connected graphs | ||
مراجع | ||
[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.
| ||
آمار تعداد مشاهده مقاله: 1,380 تعداد دریافت فایل اصل مقاله: 1,104 |