Home

Teaching

Papers

Presentations

Software

Other

MATH 412 - Graph Theory

List of Words

1. 01/14: 1.1: graph, vertex, edge, multiedge, loop, nonedge, simple graph, adjacent, neighbors, complete graph, empty graph, null graph, clique, independent set, complement, bipartite, partite sets.
2. 01/16: 1.1: chromatic number, $\chi(G)$, $k$-partite, planar, walk, trail, path, cycle, subgraph, contains, connected, disconnected, adjacency matrix $A(G)$, incidence matrix $M(G)$, incident, degree, isomorphism, isomorphic $G\cong H$, $n(G)$, $e(G)$, $P_n$, $C_n$, $K_n$, $K_{r,s}$, biclique.
3. 01/18: 1.1: self-complementary, decomposition, the Petersen graph, girth. 1.2: walk, trail, path, cycle, connected, disconnected, component.
4. 01/23: 1.2: cut-edge, cut-vertex, induced subgraph, $G[S]$, induced by, necessary, sufficient, odd/even walk, bipartition, $X,Y$-bigraph, characterization of bipartite graphs.
5. 01/25: 1.2: Eulerian circuit, Eulerian graph, even graph, maximal path, extremality, nontrivial component, characterization of Eulerian graphs.
6. 01/28: 1.3: degree, $d_G(v)$, $d(v)$, $\Delta(G)$, $\delta(G)$, regular, $k$-regular, neighborhood, $N_G(v)$, $N(v)$, order, $n(G)$, size, $e(G)$, Degree-Sum Formula, $k$-dimentional cube, $Q_k$, hypercube, $j$-dimensional subcube, sharpness, disjoint union.
7. 01/30: 1.3: $H$-free, Mantel's theorem, degree sequence, graphic, realization/realizes, Havel-Hakimi Theorem.
8. 02/01: 1.4: Directed graph, digraph, head, tail, predecessor, successor, out-degree $d^+(v)$, in-degree $d^-(v)$, total degree, $\delta^+(G), \delta^-(G), \Delta^+(G), \Delta^-(G)$, directed walk/trail/path/cycle, weakly connected, strongly connected, strong components, Eulerian digraph, deBruijn cycle.
9. 02/04: 1.4: orientation, oriented graph, tournament, king. 2.1: acyclic, forest, tree, leaf, star, spanning subgraph, spanning tree, Characterization of Trees
10. 02/06: 2.1: distance $d(u,v)$, diameter $\operatorname{diam} G$, eccentricity $\varepsilon(v)$, radius $\operatorname{rad} G$, center, Wiener index $D(G)$.
11. 02/08: 2.2: Matrix Tree Theorem.
12. 02/11: 2.2: Tree Packing Conjecture, Graceful labelings, Graceful Tree Conjecture, caterpillars.
13. 02/13: 2.3: Weighted graph, Minimum-weight spanning tree, Kruskal's Algorithm, Prim's Algorithm, Distance in Weighted Graph, Dijkstra's Algorithm.
14. 02/15: 2.3: Breadth-First-Search, Rooted Tree, root, parent, child, ancestor, descendant, subtree, left/right child, binary tree, $k$-ary tree, prefix-free code, entropy, Huffman's Algorithm.
15. 02/18: 3.1: matching, perfect matching, saturated/unsaturated vertex, maximal vs. maximum matching, $M$-alternating path, $M$-augmenting path, Hall's condition, Hall's Theorem.