UPM Institutional Repository

On the Higher Order Edge-Connectivity of Complete Multipartite Graphs


Peng, Y. H. and Chen, C. C. and Koh, K. M. (1989) On the Higher Order Edge-Connectivity of Complete Multipartite Graphs. Pertanika, 12 (1). pp. 83-88.


Let G be a connected graph with p ≥ 2 vertices. For k = 1, 2, ..., P-1, the Kth order edge-connectivity of G, denoted by A(K} (e), is defined to be the smallest number of edges whose removal from e leaves a graph with k + 1 connected components. In this note we determine A(K} (e) for any complete multi partite graph G as a consequence, we give a necessary and sufficient condition for the graph Gn to be factored into spanning trees.

Download File


Download (2MB)

Additional Metadata

Item Type: Article
Keywords: kth order edge-connectivity, efficient k-separation, complete multipartite graph, edge-toughness
Depositing User: Nur Izzati Mohd Zaki
Date Deposited: 17 Nov 2009 06:16
Last Modified: 27 May 2013 07:03
URI: http://psasir.upm.edu.my/id/eprint/2765
Statistic Details: View Download Statistic

Actions (login required)

View Item View Item