Notes on Graph Theory

Preliminary definitions for sets

subset: `A subset B`. "Set A is said to be a subset of Set B if all the elements of Set A are also present in Set B. In other words, set A is containted inside Set B." " A subset can be equal to the set."
proper subset: `A subseteq B`. "Set A is considered to be aproper subset of Set B if Set B contains at least one element that is not present in Set A.". `A subset B, A != B`

Definitions (quoted part) taken from:

Subsets- Definition, Symbol, Proper and Improper Subset | Power Set

Notation

G: case letters are used to represent a graph.
V(G): vertices of graph `G`.
E(G): edges of graph `G`.
G[S]: subgraph of `G` induced by set of vertices `S`. Alternative notation: `<<S>>_G`
G[X]: TODO

Definitions

These are definition taken from book A First Course in Graph Theory, by Gary Chartrand and Ping Zhang.

graph: TODO
vertex: TODO
edge: TODO
adjacent vertices: Given two vertices, `u` and `v`, "If `uv` is an edge in `G`, then `u` and `v` are said to be adjacent in `G`." [1.1] (a.k.a. neighbors [1.2])
order of a graph: Number of vertices in the graph. [1.1]
size of a graph: Number of edges in the graph. [1.1]
incident vertex and edge: if a vertex `v` is connected to an edge `e`, then vertex `v` and edge `e` "are said to be indicent with each other". [1.2]
adjacent edges: "Distinct edges incident with a common vertex are adjacent edges". [1.2]
subgraph: A graph H is called a subgraph of a graph G if H contains a subset of vertices and edges of G. `H subseteq G`, if `V(H) subseteq V(G)` and `E(H) subseteq E(G)`. [1.2]
proper subgraph: "If `H subseteq G` and either `V(H)` is a proper subset of `V(G)` or `E(H)` is a proper subset of `E(G)`, then `H` is a proper subgraph of G."
induced subgraph: Given a graph `G`, a graph `F` is an induced subgraph of a graph `G` if, for every vertex pair `u,v` common to both `G` and `F`, every edge `uv` that exists in `G`, also exists in `F`. In other words: "A subgraph `F` of a graph `G` is called an induced subgraph of `G` if whenever `u` and `v` are vertices of `F` and `uv` is an edge of G, then `uv` is an edge of F as well." "If `S` is a nonempty set of vertices of a graph `G`, then the subgraph of `G` induced by `S` is the induced subgraph with vertex set S. This induced subgraph is denoted by `G[S]`." [1.2]
edge-induced subgraph: Given a graph `G` and a subset of its edges `X`, the subgraph `G[X]` "consists of all vertices that are incident with at least one edge in `X`." [1.2]
walk: "A `u` -- `v` walk walk in `G` is a sequencie of vertices in `G` beginning with `u` and ending at `v`." [1.2]. (Portuguese: "passeio").
closed walk: A closed walk is a `u` -- `v` walk where `u = v`. [1.2]
open walk: A open walk is a `u` -- `v` walk in which `u != v`. [1.2]
length of a walk: Number of edges in a walk. [1.2]
trail: A `u` -- `v` trail is a `u` -- `v` walk in which no edge is traversed more than once. [1.2]. (Portuguese: "trilha").
path: A `u` -- `v` path is a `u` -- `v` walk in which no vertex is repeated. [1.2]. (Portuguese: "caminho").
circuit: "A circuit in a graph G is a closed trail of length 3 or more." [1.2]
cycle: "A circuit that repeats no vertex, except for the first and last, is a cycle. A k-cycle is a cycle of length `k`. A 3-cycle is also referred to as a triangle." [1.2]
connected vertices: "saying that `u` and `v` are connected only means that there is some `u` -- `v` path in `G`; it doesn't say that `u` and `v` are joined by an edge." [1.2]
connected graph: "A graph `G` is connected if every two vertices of `G` are connected" [1.2]
disconnected graph: A graph that is not connected. [1.2]
distance: The length of the path between two connected vertices. [1.2]
geodesic: The shortest path between two vertices, if they are connected. [1.2]
diameter: The greatest distance between two vertices of a connected graph. [1.2]

Commom problem types

If you sets ´U = {u_1, u_2, ..., u_l}´ and ´S = {S_1, S_2, ..., S_h}´ where ´S´ , we have the following problems.

Let ´T ⊆ S´.

Graph covering: (pt: Cobertura em grafos): Minimize ´T´ such as ´T = ⋃_(i=1)^h S_r_i = U´.
Graph packing: (pt: Empacotamento em grafos): Maximize ´T´ such as ´T = S_r_i ⋂ S_r_j = ∅´.
Graph partitioning: (pt: Particionamento em grafos): ´T´ is both a covering and a packing.

Coloring

Let ´C_i ⊆ V(G)´, partition ´V(G)´ into independent sets:

Covering: ´⋃_(i=1)^k C_i = V(G)´.

Packing: ´C_i ⋂ C_j = ∅´ .

References

A First Course in Graph Theory, by Gary Chartrand and Ping Zhang