Graph Theory  Assignment 7

Graph Theory 
Assignment 7
1. We consider trying to draw 𝑄𝑘 graphs on surfaces.
A. Show that 𝑄3 can be drawn on the plane without edges crossing. The quickest way is to actually
draw it.
B. Use the fact that 𝑄4 has no triangles as subgraphs and an edge counting argument similar to
that used for 𝐾3,3 to show that 𝑄4 cannot be drawn on the plane without edges crossing. Some
data to recall: 𝑄4 has 𝑛 = 16 vertices and 𝑚 = 32 edges. What would 𝑟 have to be in Euler’s
equation?
C. The graph 𝑄4 is isomorphic to 𝐶4 × 𝐶4. Use this fact to draw 𝑄4 on the torus, using the
representation in Figure 1.
Figure 1. A representation of the one-holed torus.
D. Recall that the graph 𝑄5 has 𝑛 = 32 vertices and 𝑚 = 80 edges. Since 𝑄5 is bipartite, there are
no triangles as subgraphs. Use a total edge count argument to show that 𝑟 ≤ 40. If you feed
this information into Euler’s equation 𝑛 − 𝑚 + 𝑟 = 2 − 2ℎ for the ℎ-holed torus, find a lower
bound on ℎ.
2. Draw 𝐾4,4 on a torus without the edges crossing. Here’s a suggested layout for the parts; join every
black vertex to every white vertex.
Figure 2. Starting layout for 𝐾4,4 on a torus.
3. The tournament in Figure 3 shows the outcome of a round-robin event among five competitors.
Recall that an arc from 𝑢 to 𝑤 means 𝑢 defeated 𝑤 in their match.
Figure 3. Round-robin tournament among five competitors 𝑎, 𝑏, 𝑐, 𝑑, 𝑒.
A. Form the victory matrix 𝐴 for this tournament.
B. Let 𝐰0 = 𝟏 be the all-ones vector and define 𝐰𝑖+1 = 𝐴𝐰𝑖
. Compute 𝐰𝑖
for enough values of 𝑖
to see a ranking stabilize. Suggestion: Automate this process.
C. Use an online matrix calculator (e.g. https://matrixcalc.org ) to find the eigenvector for the
principal eigenvalue (this eigenvalue is about 1.395.) This eigenvector should provide the same
ranking as your answer in part B.
𝑎
𝑏
𝑐 𝑑
𝑒
4. Consider the digraph 𝐷 depicted in figure 4.
A. Compute its incidence matrix 𝑀
B. Compute its Laplacian matrix 𝐿
1
2
3
4
5
6
10
9
8
7