Download presentation

Presentation is loading. Please wait.

Published byShirley Gain Modified over 6 years ago

1
Edge-connectivity and super edge-connectivity of P 2 -path graphs Camino Balbuena, Daniela Ferrero Discrete Mathematics 269 (2003) 13 – 20

2
Outline Introduction Introduction P 2 -path graph P 2 -path graph Result Result Review:Line Graph Review:Line Graph

3
Introduction A graph G is called connected if every pair of vertices is joined by a path. An edge cut in a graph G is a set T of edges of G such that G − T is not connected.

4
Introduction If T is a minimal edge cut of a connected graph G, then, G − T necessarily contains exactly two components. It is usual to denote an edge cut T as (C, Ĉ ), where C is a proper subset of V(G) and (C, Ĉ ) denotes the set of edges between C and its complement Ĉ.

5
Introduction A minimum edge cut (C, Ĉ ) is called trivial if C = {v} or Ĉ = {v} for some vertex v of deg(v) = (G). The edge-connectivity, (G), of a graph G is the minimum cardinality of an edge cut of G.

6
Introduction A graph G is said to be maximally edge-connected when (G) = (G). A maximally edge-connected graph is called super- if every edge cut (C, Ĉ ) of cardinality (G) satisfes that either |C|=1 or | Ĉ |=1.

7
Introduction 1 (G) = min{|(C, Ĉ )|, (C, Ĉ ) is a nontrivial edge cut}. (conditional) A graph G is super- if and only if 1 (G)> (G). The edge-superconnectivity of a graph G is the value of 1 (G).

8
Introduction Furthermore, 1 (G) min{deg(u) + deg(v), e=uv ∈ E(G)}−2=M. G is said to be optimum super-, if every minimum nontrivial edge cut is the set of edges incident with some edge of G. In this case, 1 (G) = M 2(G) − 2.

9
P 2 -path graph Given a graph G, the vertex set of the P 2 (G)-path graph is the set of all paths of length two of G. Two vertices of P 2 (G) are joined by an edge, if and only if, the intersection of the corresponding paths form an edge of G, and their union forms either a cycle or a path of length 3.

10
14 23 Example:

11
P 2 -path graph Path graphs were investigated by Broersma and Hoede [6] as a natural generalization of line graphs.

12
P 2 -path graph Theorem A:(M. Knor, 2001) Let G be a connected graph. Then P 2 (G) is disconnected if and only if G contains two distinct paths A and B of length two, such that the degrees of both end vertices of A are 1 in G.

13
By Theorem A If G is a connected graph with at most one vertex of degree one, then P 2 (G) is also connected. Result 1:Theorem 2.1 ( (G)2, (G) 2 )

14
Result (Theorem 2.1) Let G be a connected graph with (G)2. Then, (a) (P 2 (G)) (G) − 1, (b) (P 2 (G)) 2 (G) − 2 if (G) 2. Note: (P 2 (G))=2(G)−2 for regular graphs (P 2 (G))2(G)−2 in general Best possible at least for regular graphs

15
Result (Theorem 2.2) Let G be a graph with (G) 3, such that (P 2 (G))=2(G)−2. Then P 2 (G) is super- and 1 (P 2 (G)) 3((G) − 1). Note: about superconnectivity

16
Result (Theorem 2.3) Let G be a -regular graph with (G) 4. Then P 2 (G) is optimum super- and 1 (P 2 (G)) = 4 − 6. Note: about optimum super-

17
Line graph (Definition) The line graph of a graph G, written L(G), is the graph whose vertices are the edges of G, with ef E(L(G)) when e=uv and f=vw in G.

18
If G=L(H) and H is simple, then each v V(H) with d(v)2 generates a clique Q(v) in G corresponding to edges incident to v. These cliques partition E(G). Each vertex e V(G) belongs only to the cliques generated by the two endpoints of e E(H) Not a line graph

19
Property 1 (Krausz, 1943) For a simple graph G, there is a solution to L(H)=G if and only if G decomposes into complete subgraphs, with each vertex of G appearing in at most two in the list.

20
Property 2 (van Rooij and Wilf, 1965) For a simple graph G, there is a solution to L(H)=G if and only if G is claw-free and no double triangle of G has two odd triangles. An induced kite is a double triangle; it consists of two triangles sharing an edge, and the two vertices not in that edge are nonadjacent. T is odd if |N(v) V(T)| is odd for some v V(G) T is even if |N(v) V(T)| is even for every v V(G)

21
Property 3 (Beineke, 1968) A simple graph G is the line graph of some simple graph if and only if G does not have any of the nine graphs below as an induced subgraph.

22
local equality Menger stated the local equality(x,y)= (x,y) (x,y): the minimum size of an x,y-cut. (x,y): the maximum size of a set of pairwise internally disjoint x,y-paths.

23
Theorem ( ’ (x,y)= ’ (x,y)) If x and y are distinct vertices of a graph G, then the minimum size of an x, y-disconnecting set of edges equals the maximum number of pairwise edge-disjoint x, y-paths.

24
Ford-Fulkerson, 1956 ’ G (x,y)= L(G’) (sx,yt)= L(G’) (sx,yt)= ’ G (x,y)

25
local equality ’ (x,y): the maximum size of a set of pairwise edge-disjoint x,y-paths ’ (x,y): the minimum number of edges whose deletion makes y unreachable from x. Ford-Fulkerson proved that always ’ (x,y)= ’ (x,y)

26
Lemma Deletion of an edge reduces connectivity by at most 1

27
Theorem The connectivity of G equals the maximum such that (x,y) for all x,y V(G). The edge-connectivity of G equals the maximum such that ’ (x,y) for all x,y V(G).

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