Edge Connectivity Problems in Telecommunication Networks

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

Journal of ICT Research and Applications
Vol. 6 No. 3 (2012)

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.