Edge Connectivity Problems in Telecommunication Networks

Antonius Suhartomo

doi:10.5614/itbj.ict.2012.6.3.3

Authors

Antonius Suhartomo Study Program of Electrical Engineering, Faculty of Engineering, President University Jalan Ki Hajar Dewantoro, Kota Jababeka, Bekasi 17550, Indonesia

DOI:

https://doi.org/10.5614/itbj.ict.2012.6.3.3

Abstract

If a communication network N with n stations has every station linked with at least [n/2] other stations, then the edge-connectivity of N equals its minimum degree. Also, in general, this limitation is stated to be the best possibility, as was proved by Chartrand in 1966. A more developed notion of edge-connectivity is introduced, which is called k-component order edge connectivity. It is the minimum number of edges required to be removed so that the order of each disconnected component is less than k.

Downloads

Download data is not yet available.

References

Chartrand, G. A Graph-theoretic Approach to a Communications Problem, SIAM J. Appl. Math., 14, pp. 778-781D, 1966.

Boesch, F., Gross, D., Kazmierczak, L., Suhartomo, A. & Suffel, C., Component Order Edge Connectivity-An Introduction, Congressus Numerantium, 178, pp. 7-14, 2006.

Suhartomo, A., Component Order Edge Connectivity: A Vulnerability Parameter for Communication Networks, Doctoral Thesis, Stevens Institute of Technology, Hoboken NJ, May 2007.

Boesch, F., Gross, D., Suffel, C., Saccoman, J.T., Kazmierczak, L.W. & Suhartomo, A., A Generalization of A Theorem of Chartrand, Networks, 2009. doi:10.1002/net.20297.

Plesnik, J. & Znam, S., On Equality of Edge - Connectivity and Minimum Degree of Graph, Archivum Mathematicum (BRNO), 25(1-2), pp. 19-26, 1989.