Discrete Mathematical Structures by Pearson

Topics in Graph Theory 10-17

is the graph G′ given by

abG′

cd

10.5.1 Sum of Two Graphs

The sum of two graphs G

1

= (V

1

, E

1

) and G

2

= (V

2

, E

2

) denoted by G

1

+ G

2

is defined as the graph

G = (V, E) if V

1

∩ V

2

= F and the vertex set V is the V

1

∪ V

2

and the edge set E consists of edges

E

1

and E

2

and the edges joining each vertex of v

1

with each vertex of v

2

.

Let

1.

c

d

a

b

G

2

G

1

G

1

+ G

2

ac

db

2.

a

b

G

2

G

1

G

1

+ G

2

c

d

e

c

d

e

a

b

10.5.2  Cut-sets and Cut-vertices

Cut-sets play an important role in the design of communication systems of laying out telephone

cables, transportation network of roads, bridges and water supply systems. The cut-sets are used

to identify weak spots ...