Edge Connectivity Problems in Telecommunication Networks

Antonius Suhartomo


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.

Full Text:



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.

DOI: http://dx.doi.org/10.5614%2Fitbj.ict.2012.6.3.3


  • There are currently no refbacks.

Contact Information:

ITB Journal Publisher, LPPM – ITB, 

Center for Research and Community Services (CRCS) Building Floor 7th, 
Jl. Ganesha No. 10 Bandung 40132, Indonesia,

Tel. +62-22-86010080,

Fax.: +62-22-86010051;

e-mail: jictra@lppm.itb.ac.id.