2 Some basic notions 2 Some basic notions 2.2 Some basic notions

2.1 Some useful classes of graphs :

Example 2.1 (Complete graph).

$K_{n}$ : $V=[n],E=\binom{V}{2}.$

Figure 2.1: Complete graph on

5

vertices

Example 2.2 (Cayley graphs).

Let $(H,+)$ be a finite group with a finite set of generators $S$ such that $S=-S$ (symmetric) and $0\notin S$ (where $0$ is the identity). The Cayley graph $G$ is defined with vertex set $V=H$ and $x\sim y$ if $x-y\in S$ . Since $S$ is symmetric, $y-x\in S$ iff $x-y\in S$ and so abelianness of the group does not matter.

Refer to caption — Figure 2.2: Cayley graph for free group generated by a and b

Example 2.3 (Intersection graph).

Let $S_{1},\ldots,S_{n}$ be subsets of a set $S$ . Define $G$ with $V=[n]$ and $i\sim j$ if $S_{i}\cap S_{j}\neq\emptyset$ .

Example 2.4 (Delaunay graph).

$P\subset\mathbb{R}^{d},d\geq 1$ - finite distinct set of points. For $y\in\mathbb{R}^{d},d(y,P):=\min_{x\in P}|x-y|$ . Define $C_{x}:=\{y:d(y,P)=|x-y|\},x\in P$ . Delaunay graph is the intersection graph on $P$ with intersecting sets $C_{x},x\in P.$ $C_{x}$ is called as the voronoi cell of $x$ .

Example 2.5 (Euclidean Lattices).

Let $B_{r}(x)$ be the closed ball of radius $r$ centered at $x$ . The $d$ -dimensional integer lattice is the intersection graph formed with $\mathbb{Z}^{d}$ as vertex set and $B_{1/2}(z),z\in\mathbb{Z}^{d}$ as the intersecting sets. Alternatively, $z\sim z^{\prime}$ if $\sum_{i=1}^{d}|z_{i}-z^{\prime}_{i}|=1$ . Show that Euclidean lattices are Cayley graphs. Find the generators of $S$ .

Exercise 2.6.

Show that every graph is an intersection graph.

2.1.1 Some graph constructions

Example 2.7 (Bi-partite graph).

Graphs $(V,E)$ such that $V=V_{1}\sqcup V_{2}$ and $E\subset V_{1}\times V_{2}$ .

Figure 2.4: Bipartite graph

Example 2.8 (Complementary graph).

Let $G=(V,E)$ be a graph. The complementary graph is $G^{c}=(V,\binom{[V]}{2}-E).$

Example 2.9 (Line graph).

Let $G=(V,E)$ be a graph. The line graph is $L(G)$ with vertex set $V=E$ and $e_{1}\sim e_{2}$ is they are adjacent in $G$ .

Example 2.10 (Petersen graph).

The vertex set of the graph is $\binom{[5]}{2}$ and $\{i,j\}\sim\{k,l\}$ if $\{i,j\}\cap\{k,l\}=\emptyset.$

Figure 2.5: Petersen graph

Exercise(A) 2.11.

Show that the Petersen graph is the complement of the line graph of $K_{5}$ .

Exercise* 2.12.

Can you find the number of edges in a Line graph $L(G)$ in terms of the number of edges in $G$ ?

Let $G$ have $n$ vertices and $m$ edges. For each vertex $v_{i}\in V(G)$ we assume its degree to be $d_{i}$ . In $L(G)$ , two vertices share an edge iff the two edges in $G$ share a common vertex. So for each choice of two distinct edges coming out of a vertex, we get a distinct edge in $L(G)$ . Thus, $|E(L(G))|=\sum_{i=1}^{n}\binom{d_{i}}{2}$ where $\binom{d_{i}}{2}=0$ if $d_{i}\leq 1$ . But

\sum_{i=1}^{n}\binom{d_{i}}{2}=\sum_{i=1}^{n}\frac{d_{i}(d_{i}-1)}{2}=\sum_{i=% 1}^{n}(\frac{d_{i}^{2}}{2}-\frac{d_{i}}{2})

Now sum of degrees of vertices is a graph is basically counting the edges twice, so finally we have,

|E(L(G))|=\frac{1}{2}\sum_{i=1}^{n}d_{i}^{2}-m