Graph Models and Terminology

Terminology

Definition 1.1

• A graph $G$ consists of two sets: $V(G)$, called the vertex set, and $E(G)$, called the edge set. An edge, denoted xy, is an unordered pair of vertices. We will often use $G=(V,E)$ as short-hand.

Definition 1.2

• The number of vertices in a graph $G$ is denoted $|V(G)|$, or more simply $|G|$. The number of edge is denoted $|E(G)|$ or $||G||$.

Definition 1.3

Let $G$ be a graph

• If xy is an edge, then x and y are the endpoints for that edge. We say x is incident to edge e if x is an endpoint of e.
• If two vertices are incident to the same edge, we say the vertices are adjacent, denoted $x~y$. Similarly, if two edges share an endpoint, we say they are neighbors and the set of all neighbors of a vertex $x$ is denoted $N(x)$.
• If two vertices (or edges) are not adjacent then we call them independent.
• If a vertex is not incident to any edge, we call it an isolated vertx.
• If both endpoints of an edge with the same vertex, then we say the edge is a loop.
• If there is more than one edge with the same endpoints, we call these multi-edges.
• If a graph has no multi-edge or loops, we call it simple.
• The degree if a vertex $v$, denoted $deg(v)$, is the number of edges incident to $v$, with a loop adding two to the degree. If the degree is even, the vertex is called even; if the degree is odd, then the vertex is odd.
• If all vertices in a graph $G$ have the same degree $k$, then $G$ is called a k-regular graph.

Definition 1.4

• A subgraph $H$ of a graph $G$ is a graph where $H$ contains some of the edges and vertices of $G$; that is, $V(H) \subseteq V(G)$ and $E(H) \subseteq E(G)$.

Definition 1.5

• Given a graph $G=(V,E)$, an induced subgraph is a subgraph $G[V']$ where $V' \subseteq V$ and every abailable edge from $G$ between the vertices in $V'$ is included.
• We say $H$ is a spanning subgraph if it contains all the vertices but not necessarily all the edges of $G$; that is, $V(H) = V(G)$ and $E(H) \subseteq E(G)$.

Digraphs

Definition 1.6

• A directed graph, or digraph, is a graph $G=(V,A)$ that consists of a vertex set $V(G)$ and an arc set $A(G)$. An arc is an ordered pair of vertices.

Definition 1.7

Let $G = (V,A)$ be a digraph

• Given an arc xy, the head is the starting vertex x and the tail is the ending vertex y.
• Given a vertex x, the in-degree of x is the number of arcs for which x is a tail, denoted $deg^{-}(x)$. The out-degree pof x is the numver of arcs for which x is the head, denoted $deg^{+}(x)$.
• The underlying graph for a digraph is the graph $G'=(V,E)$ which is formed by removing the direction the direction from each arc to form an edge.

Weighted Graphs

Definition 1.8

• A weighted graph $G=(V,E,w)$ is a graph where each of the edges has a real number associated with it. This number is referred to as the weight and denoted $w(xy)$ for the edge $xy$.

Complete Graphs

Definition 1.9

• A simple graph $G$ is complete if every pair of distinct vertices is adjacent. The complete graph on n vertices is denoted $K_{n}$.

Definition 1.10

• The clique-size of a graph, $w(G)$, is the largest inteder n such that $K_{N}$ is a subgraph of $G$ but $K_{n+1}$ is not.

Graph Complements

Definition 1.11

• Given a simple graph $G=(V,E)$, define the complement of $G$ as the graph $\overline{G} = (V,\overline{E})$, where an edge $xy\in \overline{E} \iff xy \not\in E$.

Bipartite Graphs

Definition 1.12

• A graph $G$ is bipartite if the vertices can be partitioned into teo sets $X$ and $Y$ so that every edge has one endpoint in $X$ and the other in $Y$.

Definition 1.13

• $K_{m,n}$ is the **complete bipartite graph** where $|X|=m$ and $|Y|=n$ and every vertex in $X$ is adjacent to every vertex in $X$ is adjacent to every vertex in $Y$.

Definition 1.14

• A graph $G$ is k-partite if the vertices can be partitioned into k sets $X_{1},X_{2}...X_{k}$ so that every edge has one endpoint in $X_{i}$ and the other in $X_{j}$ where $i \not= j$.

Graph Combinations

Definition 1.15

• Given two graphs $G$ and $H$ the union $G \cup H$ is the graph with vertex-set $V(G)\cup V(H)$ and edge-set $E(G) \cup E(H)$.
• If the vertex-sets are disjoint (that is $V(G)\cap V(H) = \emptyset$) then we call the disjoint union the sum, denoted $G+H$.

Definition 1.16

• The join of two graphs $G$ and $H$, denoted $G \lor H$, is the sum $G+H$ together with all edges of the form $xy$ where $x \in V(G)$ and $y \in V(H)$.

Isomorphisms

Definition 1.17

• Two graphs $G_{1}$ and $G_{2}$ are isomorphic, denoted $G_{1} \cong G_{2}$, if there exists a bijection $f:V(G_{1}) \to V(G_{2})$ so that $xy \in E(G_{1}) \iff f(x)f(y) \in E(G_{2})$.

Theorem 1.18

Assume $G_{1}$ and $G_{2}$ are isomorphic graphs. Then $G_{1}$ and $G_{2}$ must satisfy any of the properties listed below; that is, if $G_{1}$

• is connected
• has n vertices
• has m edges
• has m vertices of degree k
• has cycle of length k
• has an eulerian circuit
• has a hamiltonian cycle

then so too must $G_{2}$(where n,m, and k are non-negative integers).

Degree Sequence

Definition 1.26

• The degree sequence of a graph is a listing of the degrees of the vertices. It is customary to write these in decreasing order. If a sequence is a degree sequence of a simple graph then we call it graphical.

Theorem 1.27 (Havel-Hakimi Theorem)

• An increasing sequence $S : s_{1},s_{2},...,s_{n}(\forall n \ge 2)$ nonnegative integers is graphical if and only if the sequence $S':s_{2}-1,s_{3}-1,...,s_{s_{1}}-1,s_{s_{n+1}},...,s_{n}$ is graphical.

Erdős-Gallai theorem

• For any integers $n \ge 1$ and $d_{1} \ge ... \ge d_{n} \ge 0$, there exists a graph with $n \ge 1$ vertices with respective degrees $d_{1},...,d_{n}$ if and only if the following two conditions hold true:

  1. the integer $d_{1}+...+d_{n}$ is even
  2. for any $1 \le k \le n, d_{1}+...+d_{k}\le k(k-1)+min(k,d_{k+1})+...+min(k,d_{n})$.

  In this case we say $d_{1},...,d_{n}$ is graphic.

Score Sequenc

Definition 1.28

• The score sequence of a tournament is a listing of the out-degrees of the vertices. It is customary to write these in incresing order.

Theorem 1.30

• An increasing sequence $S:s_{1},s_{2},...,s_{n}(\forall n \ge 2)$ of nonnegative integers is a score sequnce of a tournament if and only if the sequence $S_{1}:s_{1},s_{2},...,s_{s_{n}},s_{s_{n+1}}-1,...,s_{n-1}-1$ is a score sequence.