Download presentation

1
Vertex Cut Vertex Cut: A separating set or vertex cut of a graph G is a set SV(G) such that G-S has more than one component. d f b e a g c i h

2
Connectivity Connectivity of G ((G)): The minimum size of a vertex set S such that G-S is disconnected or has only one vertex. Thus, (G) is the minimum size of vertex cut. (X) (G)=4

3
k-Connected Graph k-Connected Graph: The graph whose connectivity is at least k. (G)=2 a b c d e f g h i G is a 2-connected graph Is G a 1-connected graph ?

4
Connectivity of Kn A clique has no separating set. And, Kn- S has only one vertex for S=Kn-1 (Kn)=n-1.

5
Connectivity of Km,n Every induced subgraph that has at least one vertex from X and from Y is connected. Every separating set contains X or Y (Km,n)= min(m,n) since X and Y themselves are separating sets (or leave only one vertex). K4,3

6
Connectivity of Qk K-dimensional Hypercube Qk : K=1 K=2 K=3 K=4

7
Connectivity of Qk For k>=2, the neighbors of one vertex in Qk form a separating set. (Qk)<=k. K=1 K=2 K=3 K=4

8
Connectivity of Qk Every vertex cut has size at least k as proved by induction on k. (Qk) =k. Basic Step: For k<=1, Qk is a complete graph with k+1 vertices and has connectivity k. Induction Hypothesis: (Qk-1)=k-1. Induction Step: Consider as two copies Q and Q’ of Qk-1 plus a matching that joins corresponding vertices in Q and Q’. Let S be a vertex cut in Qk.

9
**Connectivity of Qk Case 1: Q-S is connected and Q’-S is connected.**

S contains at least one endpoint of every match pair. |S|>= 2k-1. |S|>=k for k>=2. Q Q’

10
**Connectivity of Qk Case 2: Q-S is disconnected .**

S contains at least k-1 vertices in Q. (Induction Hypothesis) |S|>=k because S contains at least 1 vertices in Q’. (If S contains no vertices of Q’, Qk-S is connected.) Q Q’

11
Harary Graph Hk,n Given 2<=k<n, place n vertices around a circle, equally spaced. Case 1: k is even. Form Hk,n by making each vertex adjacent to the nearest k/2 vertices in each direction around the circle. (Hk,n)=k. |E(Hk,n)|= kn/2 H4,8

12
Harary Graph Hk,n Case 2: k is odd and n is even. Form Hk,n by making each vertex adjacent to the nearest (k-1)/2 vertices in each direction around the circle and to the diametrically opposite vertex. (Hk,n)=k. |E(Hk,n)|= kn/2 H5,8

13
Harary Graph Hk,n (2/2) Case 3: k is odd and n is odd. Index the vertices by the integers modulo n. Form Hk,n by making each vertex adjacent to the nearest (k-1)/2 vertices in each direction around the circle and adding the edges ii+(n-1)/2 for 0<=i<=(n-1)/2. In all cases, (Hk,n)=k. 2 1 3 4 5 6 7 8 |E(Hk,n)|= kn/2 H5,9 (Hk,n)=k. |E(Hk,n)|= (kn+1)/2

14
Theorem 4.1.5 (Hk,n ) =k, and hence the minimum number of edges in a k-connected graph on n vertices is kn/2. Proof. 1. (Hk,n ) =k is proved only for the even case k=2r. (Leave the odd case as Exercise 12) 2. We need to show SV(G) with |S|<k is not a vertex cut since (Hk,n)=k. H4,8

15
Theorem 4.1.5 3. Consider u,vV-S. The original circular has a clockwise u,v-path and a counterclockwise u,v-path along the circle. 4. Let A and B be the sets of internal vertices on these two paths. 5. It suffices to show there is a u,v-path in V-S via the set A or the set B if |S|<k. . H4,8 u v A B

16
Theorem 4.1.5 6. |S|<k. S has fewer than k/2 vertices in one of A and B, say A. Deleting fewer than k/2 consecutive vertices cannot block travel in the direction of A. There is a u,v-path in V-S via the set A. u v A B H4,8

17
Theorem 4.1.5 7. Since Hk,n has kn/2 edges, we need to show a k-connected graph on n vertices has at least kn/2 edges. 8. Each vertex has k incident edge in k-connected graph. k-connected graph on n vertices has at least kn/2 vertices.

18
Disconnecting Set Disconnecting Set of Edges: A set of edges F such that G-F has more than one component. Edge-Connectivity of G (’(G)): The minimum size of a disconnecting set. k-Edge-Connected Graph: Every disconnecting set has at least k edges.

19
Edge Cut Edge Cut: Given S,TV(G), [S,T] denotes the set of edges having one endpoint in S and the other in G. An edge cut is an edge set of the form [S,V-S], where S is a nonempty proper subset of V(G). S V-S

20
**Theorem 4.1.9 If G is a simple graph, then (G)<=’(G)<= (G).**

Proof. 1. ’(G)<= (G) since the edges incident to a vertex v of minimum degree form an edge cut. 2. We need to show (G)<=’(G). 3. Consider a smallest edge cut [S,V-S]. (’(G)= |[S,V-S]|) 4. Case 1: Every vertex of S is adjacent to every vertex of V-S. ’(G)=|[S,V-S]|=|S||V-S|>=n(G)-1. ’(G)>=k(G) since (G)<=n(G)-1. 5. Case 2: there exists xS and yV-S such that (x,y)E(G).

21
Theorem 4.1.9 5. Case 2: there exists xS and yV-S such that (x,y)E(G). 6. Let T consist of all neighbors of x in V-S and all vertices of S-{x} with neighbors in V-S. 7. Every x,y-path pass through T. T is a separating set. (G)<=|T|. 8. It suffices to show |[S,V-S]|>=|T|. x T T V-S S T T y T

22
Theorem 4.1.9 9. Pick the edges from x to TV-S and one edge from each vertex of TS to V-S yields |T| distinct edges of [S,V-S]. 9. Pick the edges from x to TV-S and one edge from each vertex of TS to V-S yields |T| distinct edges of [S,V-S]. ’(G)= |[S,V-S]|>=|T|. x T T V-S S T T y T

23
**Possibility of (G)<’(G)<(G)**

24
**Theorem 4.1.11 If G is a 3-regular graph, then (G) =’(G).**

Proof. 1. Let S be a minimum vertex cut. 2. Let H1, H2 be two components of G-S. S H1 H2

25
**Theorem 4.1.11 3. Each vS has a neighbor in H1 and a neighbor in H2.**

Otherwise, S-{v} is a minimum vertex cut. 4. G is 3-regular, v cannot have two neighbors in H1 and two in H2. 5. There are three cases for v. v v v H1 H2 H1 H1 H1 H2 u Case 1 Case 2 Case 3

26
Theorem (2/2) 5. For Cases 1 and 2, delete the edge from v to a member of {H1, H2} where v has only one neighbor. 6. For Case 3, delete the edge from v to H1 and the edge from v to H2. v v v H1 H2 H1 H1 H1 H2 u Case 1 Case 2 Case 3 7. These (G) edges break all paths from H1 to H2 .

Similar presentations

© 2021 SlidePlayer.com Inc.

All rights reserved.

To make this website work, we log user data and share it with processors. To use this website, you must agree to our Privacy Policy, including cookie policy.

Ads by Google