Note on minimally k-connected graphs

Details Note on minimally k-connected graphs Note on minimally k-connected graphs

2011-03-24

arxiv.org/abs/1103.4686v1

Computer Science

Discrete Mathematics

Scientific paper

A k-tree is either a complete graph on (k+1) vertices or given a k-tree G' with n vertices, a k-tree G with (n+1) vertices can be constructed by introducing a new vertex v and picking a k-clique Q in G' and then joining each vertex u in Q. A graph G is k-edge-connected if the graph remains connected even after deleting fewer edges than k from the graph. A k-edge-connected graph G is said to be minimally k-connected if G \ {e} is no longer k-edge-connected for any edge e belongs to E(G) where E(G) denotes the set of edges of G. In this paper we find two separate O (n2) algorithms so that a minimally 2-connected graph can be obtained from a 2-tree and a minimally k-connected graph can be obtained from a k-tree. In a k-tree (k \geq 2) we find the edges which are insensitive to the k-connectivity have both their end vertices of degrees greater than or equal to k+1.This property is fully exploited to find an algorithm which reduces any k-tree to a minimally k-connected graph.

Affiliated with

Also associated with

No associations

Rating

Note on minimally k-connected graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Note on minimally k-connected graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Note on minimally k-connected graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-47141