Math Problems Vault

Problem 21.2.1

Compare the two adjacency matrices

A = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix}, \quad B = \begin{pmatrix} 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \end{pmatrix} .

Do they admit an Euler path?

?

Problem 21.2.2

Consider the adjacency matrix

A = \begin{pmatrix} 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 \end{pmatrix} .

Is there a Hamilton cycle?

?

Problem 21.2.3

(i)(ii)

Let $G$ be a graph with vertices $V_{G} = \left\{ 1,\ldots ,n_{G}\right\}$ and edges $E_{G} \subseteq V_{G} \times V_{G}$ . The $n_{G} \times n_{G}$ adjacency matrix $A_{G}$ is given by $(A_{G})_{ij} = \chi_{E_{G}}(i,j) \in \left\{ 0,1\right\}$ where $i,j \in V$ . In the following products of graphs $G_{1}$ and $G_{2}$ with $n_{G_{1}} n_{G_{2}} \times n_{G_{2}} n_{G_{2}}$ adjacency matrices. The rows and columns are indexed by $V_{G_{1}} \times V_{G_{2}}$ , where we use the ordering $(i,j) \leq (k,l)$ if $i<k$ or, $i=k$ and $j \leq l$ .

The cartesian product $G_{1} \times G_{2}$ of two graphs $G_{1}$ and $G_{2}$ is the graph with vertices

V_{G_{1} \times G_{2}} = V_{G_{1}} \times V_{G_{2}}

and edges

E_{G_{1} \times G_{2}} = \left\{ ((a,b),(a,b')) : a \in V_{G_{1}} \text{ and } (b,b') \in E_{G_{2}} \right\}

\phantom{E_{G_{1} \times G_{2}} =} \; \cup \left\{ ((a,b),(a',b)) : (a,a') \in E_{G_{1}} \text{ and } b \in V_{G_{2}} \right\} .

It follows that

(A_{G_{1} \times G_{2}})_{(i,j),(k,l)} = \delta _{ij} (A_{G_{2}})_{(k,l)} \boxplus \delta _{kl} (A_{G_{1}})_{(i,j)}

where $\boxplus$ is the usual addition with the convention that $1 \boxplus 1 = 1$ . Thus

A_{G_{1} \times G_{2}} = (A_{G_{1}} \otimes I_{n_{G_{2}}}) \boxplus (I_{n_{G_{2}}} \otimes A_{G_{2}}) .

The lexicographic product $G_{1} \bullet G_{2}$ of two graphs $G_{1}$ and $G_{2}$ is the graph with vertices

V_{G_{1} \bullet G_{2}} = V_{G_{1}} \times V_{G_{2}}

and edges

E_{G_{1} \bullet G_{2}} = \left\{ ((a,b),(a,b')) : a \in V_{G_{1}} \text{ and } (b,b') \in E_{G_{2}} \right\}

\phantom{E_{G_{1} \bullet G_{2}} =} \; \cup \left\{ ((a,b),(a',b')) : (a,a') \in E_{G_{1}} \text{ and } b,b' \in V_{G_{2}} \right\} .

Thus $E_{G_{1} \times G_{2}} \subseteq E_{G_{1} \bullet G_{2}}$ . It follows that

(A_{G_{1} \times G_{2}})_{(i,j),(k,l)} = \delta _{ij} (A_{G_{2}})_{(k,l)} \boxplus (A_{G_{1}})_{(i,j)} .

Hence

A_{G_{1} \times G_{2}} = (A_{G_{1}} \otimes \overrightarrow {1}_{n_{G_{2}}}) \boxplus (I_{n_{G_{2}}} \otimes A_{G_{2}}) .

Here $\overrightarrow {1}_{n_{G_{1}}}$ is the $n_{G_{2}} \times n_{G_{2}}$ with every entry equal to 1.

The tensor product $G_{1} \otimes G_{2}$ of two graphs $G_{1}$ and $G_{2}$ is the graph with vertices

V_{G_{1} \otimes G_{2}} = V_{G_{1}} \times V_{G_{2}}

and edges

E_{G_{1} \otimes G_{2}} = \left\{ ((a,b),(a',b')) : (a,a') \in E_{G_{1}} \text{ and } (b,b') \in E_{G_{2}} \right\} .

It follows that

(A_{G_{1} \otimes G_{2}})_{(i,j),(k,l)} = (A_{G_{1}})_{(i,j)} (A_{G_{2}})_{(k,l)} = (A_{G_{1}} \otimes A_{G_{2}})_{(i-1)n_{G_{2}}+k,(j-1)n_{G_{2}}+l} .

Thus $A_{G_{1} \otimes G_{2}} = A_{G_{1}} \otimes A_{G_{2}}$ where $\otimes$ is the Kronecker product of matrices.

The normal product $G_{1} \star G_{2}$ of two graphs $G_{1}$ and $G_{2}$ is the graph with vertices

V_{G_{1} \star G_{2}} = V_{G_{1}} \times V_{G_{2}}

and edges

E_{G_{1} \star G_{2}} = E_{G_{1} \times G_{2}} \cup E_{G_{1} \otimes G_{2}} .

Thus

A_{G_{1} \star G_{2}} = A_{G_{1} \times G_{2}} \boxplus A_{G_{1} \otimes G_{2}} = (A_{G_{1}} \otimes I_{n_{G_{2}}}) \boxplus (I_{n_{G_{2}}} \otimes A_{G_{2}}) \boxplus A_{G_{1}} \otimes A_{G_{2}} .

?

(i)

Show that the Euler path is not preserved (in general) under these operations.

(ii)

Show that the Hamilton path is not preserved (in general) under these operations.