12.5 Exercises

Let $G$ be a graph with incidence matrix ${\partial }_1$ and let $B={(b_{ij})}_{i,j\le k}$ be a $(k\times k)$-submatrix of ${\partial }_1$ which is nonsingular. Show that there is precisely one permutation $\sigma$ of $1,\mathrm{\dots },k$ such that the product ${\prod }_{i=1}^k{b}_{i{\sigma }_i}$ is non-zero.

Let ${\delta }_i={\partial }_i^T$ be the transpose of the incidence matrices ${\partial }_i$ for $i=0,1$. Show that ${\delta }_i$ defines a linear map from $C_{i-1}$ to $C_i$ where $C_{-1}=𝔽$, the underlying field. Further show that ${\delta }_1\circ {\delta }_0=0$. Describe the spaces $Im({\delta }_i),Ker({\delta }_i)$ for $i=0,1$. Can you express the number of connected components in terms of the ranks of these spaces ?

Let $G$ be a graph with $k$ components. Suppose $B$ is a $(l\times l)$- submatrix of the incidence matrix ${\partial }_1$ indexed by $\{e_1,\mathrm{\dots },e_l\}$ and rows by $\{v_1,\mathrm{\dots },v_l\}$. Show that $B$ is a non-singular matrix only if $l\le r({\partial }_1)$ and $\{e_1,\mathrm{\dots },e_l\}$ form a forest on $\{v_1,\mathrm{\dots },v_l\}$. What is the subgraph $\{e_1,\mathrm{\dots },e_l\}$ when $l=r({\partial }_1)$ ?

Compute the eigenvalues of the Laplacian and Adjacency matrices of the the cycle graph and the path graph.

Let $G$ be a graph with $n$ vertices, $m$ edges and let ${\lambda }_1\ge \mathrm{\dots }{\lambda }_n$ be the eigenvalues of the adjacency matrix of $G$. Show the following bounds for the eigenvalues

1. (a)

   ${\lambda }_1\le \sqrt{\frac{2m(n-1)}{n}}$

2. (b)

   $\delta (G)\le {\lambda }_1\le \mathrm{\Delta }(G).$

3. (c)

   If $H$ is an induced subgraph on $p$ vertices then

   $${\lambda }_n(G)\le {\lambda }_p(H)\le {\lambda }_1(H)\le {\lambda }_1(G).$$

Let $G$ be a connected graph on $n$ vertices and $m$ edges. Let ${\partial }_1$ be its incidence matrix under a fixed orientation of edges. Let $y={(y_1,\mathrm{\dots },y_n)}^T$ be a $(n\times 1)$-column vector such that for some $i\ne j\in [n]$, $y_i=+1,y_j=-1$ and $y_l=0$ for $l\in [n]\setminus \{i,j\}$. Show that there exists a $(m\times 1)$-column vector $x$ such that ${\partial }_{1}x=y$. Give a graph-theoretic interpretation of the same.

Let ${\lambda }_1\le \mathrm{\dots }\le {\lambda }_n$ be the eigenvalues of $L$. Compute the eigenvalues of $L+aJ$ for $a>0$ where $J$ is the all $1$ matrix.

Compute the eigenvalues of the laplacian matrix $L$ and adjacency matrix $A$ of the Petersen graph. Calculate the number of spanning trees of the Petersen graph. (Hint : Show that $A^2+A-2I=J$)

Compute the eigenvalues of $L(G\times H)$ in terms of $L(G)$ and $L(H)$ where $G\times H$ is the cartesian product of $G$ and $H$.