Graph Theory Midterm 1

Finite graph

A _____ G consists of 2 finite sets V & E, V vertex set, E edge set

Order

the ____ of a graph G = (V, E) is the # of vertices in G denoted |V(G)|

Size

the ____ of a graph G = (V, E) is the # of edges in G denoted |E(G)|

Adjacent

vertices u,v \in V are _____ if uv \in E

Incident

vertex v \in V is _____ to e if v is an endpoint of e

Neighborhood - N(v)

the ____ of v \in V is the set of all vertices adjacent to v, Given S \subseteq V, the ____ of S is the union of ______ of vertices in S

Degree - deg(v)

the ____ of a vertex v \in V is the # of edges incident to v. In a simple graph ____ = |N(v)|

Max Degree - ∆(G)

= max{deg(v)

Min Degree - δ(G)

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

Degree Sequence

the ____ of a graph order n is an n-term seq of vertex degrees

Walk

a ____ in a graph G is a seq of vertices v1, v2, …, vk s.t. Vivi+1 \in E for i = 1, 2, …, k.

Path

If vertices in a walk are distinct

Trail

If edges in a walk are distinct

Cycle

a closed path, a walk v1 v2 …. Vk v1 w/ k >= 3 and v1 …. Vk is a path

Circuit

a closed trail that begins and ends at the same vertex

Length of a walk

total # of edges in the walk

Connected

A graph is ____ if every pair of vertices can be joined by a path

Cut vertex

a vertex v is a _____ if G-v has more connected components than G

Bridge

an edge e is a ____ if G - e has more connected components than G

Cut set

S \subseteq E is an (edge) ____ if G - S has more connected components than G

Complete - K_n (order n)

A graph G is ___ if every pair of vertices in G is adjacent

Connectivity - K(G)

For a non compete graph G, the ____ of G is the minimum size of a vertex cut set of G. If G is not complete 1<=___<=2, if G is disconnected ___ = 0

K-connected

For positive integers k, we say a graph G is _____ if k <= k(G)

Complement graph - G bar

the _____ graph of a graph G is the graph w/ same vertex set as G, and consisting of all possible edges not present in G

Regular graph - k-regular

graph G is _____ of degree k if all vertices have degree k.

Subgraph

Graph H is a ____ of graph G if V(H) \subseteq V(G) and E(H) \subseteq E(G), write H \subseteq G

Induced subgraphs

given G = (V, E) and a subset of vertices S \subseteq V, the subgraph of G ____ by S, <S>, is the subgraph H of G w/ vertex set S and edge set the edges in G w/ vertices in S

• V(H) = S

• E(H) = {uv : u, v \in S and uv \in E(G)}

Bipartite graph

graph G is a _____ if the vertex set V(G) can be partitioned into 2 disjoint sets X & Y s.t. Every edge of G has exactly 1 vertex in X and 1 in Y A complete _____ is one such that every x \in X and y \in Y are adjacent

Star Graph

A bipartite graph K_{1,k}

Line Graph - L(G)

the _____ of a graph G is the graph w/ vertices of ____ are the edges in G, (V(___) = E(G)) and 2 vertices are adjacent in ___ if the corr edges in G share a vertex

Isomorphic graphs

Graphs G and H are _____ if there is a mapping from the vertex set of one to the vertex set of the other that preserves adjacencies

Distance - d(u,v)

in a connected graph G, the ____ between vertices u,v \in V(G) is defined to be the length of a shortest length u-v path in G, Is infinity if G is disconnected

Eccentricity - ecc(v)

= max{d(v,x)} x \in V(G), or maximum distance from v to any other vertex

Radius - rad(G)

= min{ecc(x)} x \in V(G), value of smallest ecc.

Diameter - Diam(G)

= max{ecc(x)} x \in V(G), value of largest ecc.

Center - C(G)

= {x \in V(G) | ecc(x) = rad(G)}

Periphery - Per(G)

= {x \in V(G) | ecc(x) = diam(G)}

Self Centered

If V(G) = C(G)

Adjacency matrix

the ______ of G is the nxn matrix A w/ entry in the ith row and jth column defined by A_ij = {1 if vi & j are adjacent, 0 otherwise}

Cumulative walk matrix

Sk = I + A + A^2 + … + A^k

Distance matrix

the _____ of G is the nxn matrix D defined by Dij = d(vi, vj)

Tree

a ____ is a connected graph that contains no cycles

Leaf

a vertex of degree 1 in a tree

Forest

a graph is a _____ if each of its connected comps is a tree

Spanning tree

given a graph G and a subgraph tree T of G, T is a ______ if V(T) = V(G)

Weighted graphs

given a graph G, a weight function on G is a function, W E(G) → [0, infinity)

Min weight spanning tree

A connected graph G, a ____ of G is a spanning tree T of G st the sum of the edges of T is minimal

Kruskal’s Algorithm

find min weight spanning tree of connected graph G Find edge of min wt and mark it Among all edges that don't form a cycle with the marked edge, chose edge of min e=wt and mark it Repeat until a spanning tree is obtained