image Graph Theory Lessons image

rule

previous index next Lesson 34: Unions and Sums of Graphs

There are several ways to combine two graphs to get a third one. Suppose we have graphs G1 and G2 and suppose that G1 has vertex set V1 and edge set E1, and that G2 has vertex set V2 and edge set E2. The union of the two graphs, written G1 ∪ G 2 will have vertex set V1 ∪ V2 and edge set E1∪ E2.

Petersen Activity:
To get the union of two graphs in the Petersen program, Operations | Union . You will get a widget that looks like figure 34.1 that you can use to choose the left and right graph.

widget to create a union of graphs
Fig 34.1
If, for instance, you choose the null graph N1 for the left side and the complete graph K5 for the right you will get the graph in figure 34.2.
Fig 34.2, the union N1 ∪ K5
.

The sum of two graphs G1 and G2, written G1 + G2, is obtained by first forming the union G1 ∪ G2 and then making every vertex of G1 adjacent to every vertex of G2.

Petersen Activity:
To get the sum of two graphs in the Petersen program, Operations | Sum. Again you will get a widget that looks like figure 34.1 that you can use to choose the left and right graph. If, for instance, you choose the null graph N1 for the left side and the complete graph K5 for the right you will get the graph in figure 34.3.

Fig 34.3, the sum N1 + K5
.

  1. Which graph is isomorphic to Kn + N1?
  2. Which graph is isomorphic to Kn + Km?
  3. Which graph is isomorphic to Nr + N1?
  4. Which graph is isomorphic to Nr + Ns?
  5. Which graph is isomorphic to Nr ∪ Ns?
  6. Which graph is isomorphic to Nr + Ns + Nt?
  7. Which graph is isomorphic to the sum Cn+ N1 of a circuit graph on n vertices and a null graph on 1 vertex?
  8. If G1 has chromatic number Χ(G1) = a and Χ(G2) = b, then what is Χ(G1 ∪ G2)? (You might have to do some experiments in Petersen to give you some ideas).
  9. If Χ(G1) = a and Χ(G2) = b, then what is Χ(G1 + G2)?

Answers


© C. Mawata