Exam 10: Graphs

In questions fill in the blanks.1113:1156 -Determine whether the graph is strongly connected, and if not, whether it is weakly connected.

Find the vertex-chromatic number, the edge-chromatic number, and the region-chromatic number for $K _ { 4 }$

Explain how graphs can be used to model the spread of a contagious disease. Should the edges be directed or undirected? Should multiple edges be allowed? Should loops be allowed?

Draw a cubic graph with 6 vertices that is not isomorphic to $K _ { 3,3 }$ or else prove that there are none.

In $K _ { 3,3 }$ let a and b be any two adjacent vertices. Find the number of paths between a and b of length 5.

In questions either give an example or prove that there are none. -A graph with 9 vertices with edge-chromatic number equal to 2.

Find the vertex-chromatic number, the edge-chromatic number, and the region-chromatic number for $C _ { 7 }$

In questions either give an example or prove that there are none. -A planar graph with 10 vertices.

Find the vertex-chromatic number, the edge-chromatic number, and the region-chromatic number for $K _ { 3.2 }$

In questions fill in the blanks.1113:1156 -The length of the longest simple circuit in $K _ { 4,10 } \text { is }$ .

In questions fill in the blanks.1113:1156 - $\text { List all positive integers } n \text { such that } W _ { n } \text { has a Hamilton circuit. }$$\underline{\quad\quad}$

In questions fill in the blanks.1113:1156 -There are 0's and 1's in the adjacency matrix for Cn.

In questions fill in the blanks.1113:1156 - $\text { Every Hamilton circuit for } W _ { n } \text { has length }$$\underline{\quad\quad}$

In questions fill in the blanks.1113:1156 - $\text { The largest value of } n \text { for which } K _ { 6 , n } \text { is planar is }$$\underline{\quad\quad}$

In questions fill in the blanks.1113:1156 -There are non-isomorphic simple undirected graphs with 5 vertices and 3 edges.

Find the vertex-chromatic number, the edge-chromatic number, and the region-chromatic number for $Q _ { 3 }$

Draw the undirected graph with adjacency matrix $\left( \begin{array} { l l l l l } 0 & 1 & 3 & 0 & 4 \\1 & 2 & 1 & 3 & 0 \\3 & 1 & 1 & 0 & 1 \\0 & 3 & 0 & 0 & 2 \\4 & 0 & 1 & 2 & 3\end{array} \right)$

Are these two digraphs isomorphic?

In questions fill in the blanks.1113:1156 -The incidence matrix for $W _ { n }$ has $\underline{\quad\quad}$ rows and $\underline{\quad\quad}$ columns.

In $K _ { 5 }$ find the number of paths of length 6 between every pair of vertices.