Graph Theory

\( \newcommand{\defint}[4]{\int_{#1}^{#2}\,#3\,d#4} \)

Chapter 2
Algebraic Graph Theory

2.1 Introduction

This is one of my favorite topics.

2.2 Adjacency Matrices

2.2.1 Introduction

Might as well begin here.

We can have a variety of displayed equations, basically from the amsmath package. For example, a single displayed equation, with no number, and hence no referencing is possible: \[x^2+y^2 = 25\]

We can can have a single numbered equation, so referencing is possible: \[x^4+y^4 = 81\tag{2.1}\label{eqn-diophantine}\]

Or several equations in a row, none of them numbered. \[\begin{align} a^2-b_3+6 = 123\notag\\ a^2-b_4+6 = 123\notag\\ a^2-b_7+6 = 123\notag \end{align}\]

Or several equations in a row, all of them numbered. \[\begin{align} a^2-b_3+6 = 123\tag{2.2}\\ a^2-b_4+6 = 123\tag{2.3}\\ a^2-b_7+6 = 123\tag{2.4} \end{align}\]

We can selectively not number equations in a group that are all numbered. \[\begin{align} a^2-b_3+6 = 123\label{blatzo}\tag{2.5}\\ a^2-b_4+6 = 123\label{incompatible}\notag\\ a^2-b_7+6 = 123\tag{2.6} \end{align}\]

We can selectively number equations in a group that are all unnumbered. \[\begin{align} a^2-b_3+6 = 123\notag\\ a^2-b_4+6 = 123\tag{2.7}\label{eqn-select}\\ a^2-b_7+6 = 123\notag \end{align}\]

2.2.2 The Basics

We should first make a definition.

Definition 2 Given a graph \(G\), we define the adjacency matrix \(A(G)\) as the \(0\)-\(1\) matrix given by: \[A(G)=\begin{cases} 0 &\text{ if }v_i\text{ and }v_j\text{ are adjacent}\\ 1 &\text{otherwise} \end{cases}\tag{2.8}\]

When no confusion will result, we will denote this matrix simply as \(A\).

Sample notation (in a master list eventually): \(A(G)\)

2.3 Eigenvalues

This is where the fun would start. But instead we will practice referencing some displayed equations, such as the first numbered single display, Equation~2.1 and the selectively numbered equation~2.7.

Test refs: \ref{blatzo}, \ref{incompatible}