[SOLVED] CPTS553-Assignment 4

Description

1. For the cube graph 𝑄_𝑛, the distance 𝐷(𝐚, 𝐛) between two vertices

𝐚 = (𝑎₁, 𝑎₂, … , 𝑎_𝑛) and 𝐛 = (𝑏₁, 𝑏₂, … , 𝑏_𝑛)

is called the “Hamming distance.”  This is the number of positions where 𝐚 and 𝐛 differ.  For instance, the Hamming distance between (0,0,1,0) and (1,1,0,0) is 3 because these two vertices differ in three positions.  In each of the parts A,B below, 𝐷(𝐱, 𝐲) is the Hamming distance in 𝑄_𝑛:

1. Show that if 𝐷(𝐚, 𝐛) and 𝐷(𝐛, 𝐜) have the same parity (i.e., are both even or are both odd), then 𝐷(𝐚, 𝐜) must be even.
2. Show that if 𝐷(𝐚, 𝐛) and 𝐷(𝐛, 𝐜) have different parity, then 𝐷(𝐚, 𝐜) must be odd.

2. Consider 𝐾₄ as drawn and labeled below:

Since this graph is simple, we can specify a walk by listing only the vertices.  For instance, 𝐶: 1,2,3,4,1 is a 4-cycle; this can be abbreviated as “12341”.  List all of the cycles (abbreviated style is fine) that start and end at vertex 1 in this drawing of 𝐾₄.

3. For 1 ≤ 𝑚 ≤ 11, let 𝐺_𝑚 be the graph with vertex set

𝑉 = {0,1,2,3,4,5,6,7,8,9,10,11}

and where vertices 𝑢 and 𝑤 are adjacent iff 𝑤 − 𝑢 = 𝑚 modulo 12 or 𝑢 − 𝑤 = 𝑚 modulo 12.  We observe that 𝐺₁ = 𝐶₁₂, a twelve-cycle. A.  For what values of 𝑚 is 𝐺_𝑚 connected?

1. What are the possible numbers of components of 𝐺_𝑚?

4. Let 𝐺 be a graph and let 𝑒₁ and 𝑒₂ be edges. Show that if deleting 𝑒₁ and 𝑒₂ disconnects vertices 𝑢 and 𝑣, then any cycle containing both 𝑢 and 𝑣 must contain both 𝑒₁ and 𝑒₂.  One approach:  You could apply to the graphs 𝐺 − 𝑒₁ and 𝐺 − 𝑒₂ the fact that if 𝑒 is a bridge whose removal disconnects 𝑢 and 𝑣, then any path connecting 𝑢 and 𝑣 must contain 𝑒.