Graph Theory Midterm 2

Degree matrix

the nxn diagonal matrix D = [Dij] w/ i,jth entry Dij = {deg(vi) if i = j, 0 otherwise;

Laplacian matrix

the nxn matrix defined by L = D - A, where A is the adjacency matrix of G and D is the degree matrix;

Cofactors

given an nxn matrix M, the i,jth cofactor of m is defined Cij = (-1)^{i + j}det(M(i|j)), where M(i|j) is the (n-1)x(n-1) matrix formed by deleting the ith row and jth column of M;

Trail

a walk that doesn't repeat edges;

Circuit

closed trail;

Eulerian trail

a trail in graph G that includes every edge of G;

Eulerian circuit

a circuit in G that includes every edge of G;

Eulerian graph

graphs that contain eulerian circuits;

Hamiltonian path

a path P in G such that V(P) = V(G);

Traceable

if graph contains a hamiltonian path;

Hamiltonian cycle

cycle in G if V(C) = V(G);

Hamiltonian

if G contains a hamiltonian cycle;

Minimum degree of G, δ(G)

min{deg(v)| v \in V(G)}

Independent set

set of vertices in G that are pairwise nonadj;

Independence number α(G)

size of the largest independent set of vertices in G;

H - free

if G does not contain a copy of H as an induced subgraph;

Planar

can be drawn in the plane w/ edges intersecting only at vertices;

Planar representation

drawing of planar graph;

Region

a maximal section of the plane in which any 2 points of this can be joined by a curve that lies entirely in R and does not intersect any edges or vertices of G;

Edge e is bounding

if e comes into contact w/ one region and some other region;

Bound degree b(R)

the number of edges bounding R;

Euler’s formula

If G is a connected planar graph w/ n vertices, q edges, and r regions, then, n - q + r = 2;

Is K_{3,3} nonplanar or planar? What does this imply?

nonplanar, implies K_m,n is nonplanar for m, n >= 3;

Is K_5 nonplanar or planar? What does this imply?

nonplanar, implies K_n for n >=5 is nonplanar;

Solid polyhedron

a solid bounded by flat surfaces;

Polyhedral surface

bounds a solid polyhedron, consists of faces, edges, and vertices;

Regular polyhedron

its faces are mutually congruent regular polygons w/ the # of faces meeting at each vertex the same;

Thm 1.36. How does a polyhedrons V vertices, E edges and F faces relate to each other?

V - E + F = 2;

Given polyhedron P, ρ(P)

min{b(R) | R is a region of P} = min{b(F) | F is a face of P};

Subdivision of an edge e

a substitution of a path for the edge e in G;

Subdivision of graph G, H

can be obtained from G by finite sequences of subdivisions of edges in G;

Kuratovskis thm

A graph G is planar iff it contains no subdivision of K_{3,3} or K_5;

K-coloring

a function K: V(G) —> {1, …., k}

Proper k-coloring

a k-coloring K s.t. K(u) /= K(v) for all vertices u,v \in V(G) s.t. uv \in E(G);

K-colorable

if graph G has a proper k-coloring;

Chromatic number Χ(G)

the smallest integer k s.t. G is k-colorable;

Clique number ω(G)

the order of the largest complete graph that is a subgraph of G;

Cliques

complete subgraphs of a graph G